TR01-042 | 31st May 2001 00:00
Approximating Bounded Degree Instances of NP-Hard Problems
TR01-042
Authors:
Marek Karpinski
Publication: 1st June 2001 11:21
Downloads: 2513
Keywords:
Approximation Algorithms,
Approximation Ratios,
Bounded Degree Instances,
Linear Equations,
lower bounds,
MAX-2SAT,
MAX-BISECTION,
Max-Cut,
MIN-BISECTION,
MIS,
nearest codeword problem,
Node Cover,
Semidefinite Programs,
Sorting by Reversals,
Traveling Salesman Problem
Abstract:
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.
