On the hardness of approximating max-satisfy
type: Item
instance of: scholarly article
title: On the hardness of approximating max-satisfy
zbMATH Open document ID: 1185.68350
author: Daniel Reichman
author: Uriel Feige
published in: Information Processing Letters
publication date: 2009-12-18T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5650167
zbMATH Keywords: approximation algorithms
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: j.ipl.2005.08.012
OpenAlex ID: W2044184640
cites work: Derandomized graph products
cites work: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Proof verification and the hardness of approximation problems
cites work: On the number of zero-patterns of a sequence of polynomials
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: On the complexity of approximating the independent set problem
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Q4856179
cites work: A PCP characterization of NP with optimal amortized query complexity
DOI: 10.1016/J.IPL.2005.08.012
Recommended article: On the Approximation of Maximum Satisfiability
Recommended article: Q4229151
Recommended article: Q4524463
Recommended article: On Some Recent Approximation Algorithms for MAX SAT
Recommended article: Q3129924
Recommended article: Approximation algorithms for the maximum satisfiability problem
Recommended article: MAX SAT approximation beyond the limits of polynomial-time approximation
Recommended article: On Approximation Algorithms for Hierarchical MAX-SAT
Recommended article: Q4247437
description: scientific article; zbMATH DE number 5650167