Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, Abt. V
85230

July 19, 2001

Efficient Amplifiers and Bounded Degree Optimization
Piotr Berman and Marek Karpinski
[Download PostScript] [Download PDF]

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/152 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.

Last Change: 11/05/14 at 10:20:05
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V