Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style
icon Submit Paper


RSS-Feed
REPORTS > DETAIL:

Revision(s):

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

Inapproximability of Combinatorial Optimization Problems

Contact
Add Comment
RSS-Feed




Revision #1 Authors: Luca Trevisan
Accepted on: 22nd February 2010 02:07
Downloads: 5701
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: 4147
Keywords: 


Abstract:

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


ISSN 1433-8092 | Imprint