scientific article; zbMATH DE number 6823767

DOI10.4086/TOC.2017.V013A019MaRDI QIDQ4602398zbMATH OpenOpenAlexFDO

Authors

Publication date 10 January 2018

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2017.v013a019

zbMATH Keywords

approximabilitygadgetlinear programmingunique games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• Linear Programming with Two Variables Per Inequality in Poly-Log Time
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• \(\mathcal{NP}\)-hardness of approximately solving linear equations over reals
• NP-hardness of approximately solving linear equations over reals
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Two linear approximation algorithms for convex mixed integer nonlinear programming
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems

Cited in

(6)

• Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• Gadgets, Approximation, and Linear Programming
• UG-hardness to NP-hardness by losing half
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Improved NP-inapproximability for 2-variable linear equations

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4602398)