Approximating maximum satisfiable subsystems of linear equations of bounded width

DOI10.1016/j.ipl.2007.11.011zbMath1186.68566OpenAlexW2159113540MaRDI QIDQ963367

Zeev Nutov, Daniel Reichman

Publication date: 19 April 2010

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

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

zbMATH Keywords

linear equationsapproximation algorithmssatisfiable systems

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions

Cites Work

• Unnamed Item
• Unnamed Item
• On the hardness of approximating max-satisfy
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Near-optimal algorithms for unique games
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Hardness of Learning Halfspaces with Noise
• On the power of unique 2-prover 1-round games
• Approximating unique games
• 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
• Some optimal inapproximability results