A well-characterized approximation problem

DOI10.1016/0020-0190(93)90076-LzbMath0782.68057OpenAlexW2117913620WikidataQ56959141 ScholiaQ56959141MaRDI QIDQ688442

Shmuel Safra, Steven J. Phillips, Johan T. Håstad

Publication date: 13 March 1994

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

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90076-l

zbMATH Keywords

approximation algorithmNP-hard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Polly cracker, revisited, MODp-tests, almost independence and small probability spaces, The complexity and approximability of finding maximum feasible subsystems of linear relations, PCP characterizations of NP: toward a polynomially-small error-probability, Phase transition of multivariate polynomial systems, Minimal achievable approximation ratio for MAX-MQ in finite fields

Cites Work

• Simple Constructions of Almost k-wise Independent Random Variables
• On the hardness of approximating minimization problems
• Efficient probabilistically checkable proofs and applications to approximations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item