On approximating NP-hard optimization problems

MaRDI QIDQ1126838zbMATH OpenFDO

Authors Johan Hastad

Publication date 5 August 1998

Published in Documenta Mathematica (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/DMJDMV/xvol-icm/14/Hastad.MAN.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

approximating algorithmslinear equationsNP-hard optimization problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Review text

Consider the problem of satisfying the maximal number of equations in an over-determined system of linear equations. The author shows that it is NP-hard to approximate this problem within a factor smaller than 2.

Recommendations

• On the hardness of approximating max-satisfy
• scientific article; zbMATH DE number 3902037
• scientific article; zbMATH DE number 1789921
• Some recent strong inapproximability results
• On the hardness of approximating minimization problems

Cited in

(7)

• MNP: A class of NP optimization problems
• Improving the complexities of approximation algorithms for optimization problems
• scientific article; zbMATH DE number 847149 (Why is no real title available?)
• Some recent strong inapproximability results
• Approximation algorithms for NP-hard problems
• Reoptimization of NP-Hard Problems
• Approximate solution of NP optimization problems

This page was built for publication: On approximating NP-hard optimization problems

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