Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR04-065 | 22nd February 2010 02:07

Inapproximability of Combinatorial Optimization Problems

RSS-Feed




Revision #1
Authors: Luca Trevisan
Accepted on: 22nd February 2010 02:07
Downloads: 5661
Keywords: 


Abstract:

We survey results on the hardness of approximating combinatorial
optimization problems.



Changes to previous version:

We update the survey with results from the past six years, especially on unique-games based inapproximability and on integrality gaps.


Paper:

TR04-065 | 28th July 2004 00:00

Inapproximability of Combinatorial Optimization Problems





TR04-065
Authors: Luca Trevisan
Publication: 9th August 2004 19:29
Downloads: 4110
Keywords: 


Abstract:

We survey results on the hardness of approximating combinatorial
optimization problems.



ISSN 1433-8092 | Imprint