Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2001 Copyright 2001 Universität Bonn, Institut für Informatik, Abt. V
8970

May 31, 2001

Approximating Bounded Degree Instances of NP-Hard Problems
Marek Karpinski
[Download PostScript] [Download PDF]

We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages of proving approximation hardness of some other generic optimization problems.

Last Change: 11/05/14 at 10:21:17
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope