On the hardness of approximating max-satisfy

DOI10.1016/j.ipl.2005.08.012zbMath1185.68350OpenAlexW2044184640MaRDI QIDQ1045886

Daniel Reichman, Uriel Feige

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.08.012

zbMATH Keywords

computational complexityapproximation algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Approximating maximum satisfiable subsystems of linear equations of bounded width ⋮ Pricing on Paths: A PTAS for the Highway Problem

Cites Work

• Unnamed Item
• On the complexity of approximating the independent set problem
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Derandomized graph products
• On the number of zero-patterns of a sequence of polynomials
• Proof verification and the hardness of approximation problems
• A PCP characterization of NP with optimal amortized query complexity
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques