Approximating maximum satisfiable subsystems of linear equations of bounded width
type: Item
instance of: scholarly article
title: Approximating maximum satisfiable subsystems of linear equations of bounded width
zbMATH Open document ID: 1186.68566
author: Zeev Nutov
author: Daniel Reichman
published in: Information Processing Letters
publication date: 2010-04-19T00:00:00Z
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5694933
zbMATH Keywords: linear equations
zbMATH Keywords: satisfiable systems
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: j.ipl.2007.11.011
OpenAlex ID: W2159113540
cites work: The complexity and approximability of finding maximum feasible subsystems of linear relations
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Near-optimal algorithms for unique games
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: On the hardness of approximating max-satisfy
cites work: Approximating unique games
cites work: Hardness of Learning Halfspaces with Noise
cites work: Q3549614
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Some optimal inapproximability results
cites work: On the power of unique 2-prover 1-round games
cites work: Q2721981
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1016/J.IPL.2007.11.011
Recommended article: The complexity and approximability of finding maximum feasible subsystems of linear relations
Recommended article: Q4828976
Recommended article: On the Approximation of Maximum Satisfiability
Recommended article: Sublinear-space approximation algorithms for Max \(r\)-SAT
Recommended article: MAX SAT approximation beyond the limits of polynomial-time approximation
Recommended article: Upper bounds on the complexity of solving systems of linear equations
Recommended article: Q3129924
Recommended article: Approximation algorithms for the maximum satisfiability problem
Recommended article: Q4267801
description: scientific article; zbMATH DE number 5694933