期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
