Approximating maximum satisfiable subsystems of linear equations of bounded width

DOI10.1016/J.IPL.2007.11.011MaRDI QIDQ963367zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmslinear equationssatisfiable systems

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• The complexity and approximability of finding maximum feasible subsystems of linear relations
• scientific article; zbMATH DE number 2119705
• On the Approximation of Maximum Satisfiability
• Sublinear-space approximation algorithms for Max \(r\)-SAT
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Upper bounds on the complexity of solving systems of linear equations
• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem
• scientific article; zbMATH DE number 1351079

Cites work

• scientific article; zbMATH DE number 1617261 (Why is no real title available?)
• A 3-query PCP over integers
• Approximating unique games
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Hardness of learning halfspaces with noise
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Near-optimal algorithms for unique games
• On the hardness of approximating max-satisfy
• On the power of unique 2-prover 1-round games
• Some optimal inapproximability results
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• The hardness of approximate optima in lattices, codes, and systems of linear equations

Cited in

(4)

• On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
• Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
• scientific article; zbMATH DE number 6829282 (Why is no real title available?)
• scientific article; zbMATH DE number 2119705 (Why is no real title available?)

This page was built for publication: Approximating maximum satisfiable subsystems of linear equations of bounded width

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