Approximating maximum satisfiable subsystems of linear equations of bounded width
From MaRDI portal
Publication:963367
DOI10.1016/J.IPL.2007.11.011zbMATH Open1186.68566OpenAlexW2159113540MaRDI QIDQ963367FDOQ963367
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
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
- Some optimal inapproximability results
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On the power of unique 2-prover 1-round games
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- 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
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Approximating unique games
- Near-optimal algorithms for unique games
- Hardness of learning halfspaces with noise
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- On the hardness of approximating max-satisfy
- Title not available (Why is that?)
- A 3-query PCP over integers
Cited In (4)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
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)
