DIMACS TR: 2001-42
Efficient Amplifiers and Bounded Degree Optimization
Authors: Piotr Berman and Marek Karpinski
ABSTRACT
This paper studies the existence of efficient (small size) amplifiers
for proving explicit inaproximability results for bounded degree
and bounded occurrence combinatorial optimization problems, and gives
an explicit construction for such amplifiers. We use this construction
also later to improve the currently best known approximation lower bounds
for bounded occurrence instances of linear equations mod 2, and
for bounded degree (regular) instances of MAX-CUT.
In particular we prove the approximation lower bound of 152/151 for
exactly 3-occurrence E3-OCC-E2-LIN-2 problem, and MAX-CUT problem on
3-regular graphs, E3-MAX-CUT, and the approximation lower bound
of 121/120 for E3-OCC-2-LIN-2 problem. As an application we are
able to improve also the best known approximation lower bound for
E3-OCC-MAX-E2SAT.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-42.ps.gz
DIMACS Home Page