In this thesis we study approximation-preserving reductions among combinatorial optimization problems, and we use them to prove completeness results in approximation classes, as well as stronger non-approximability results and the existence of improved approximation algorithms for specific problems.
The first part of the thesis deals with the way of correctly defining the notion of approximation preserving reducibility. Our emphasis here is on completeness results in approximation classes. Several different approximation-preserving reducibilities have been defined in the last decade. We prove that none of them allows to prove certain natural completeness results, such as the fact that the Maximum Satisfiability Problem is complete for the class of problems approximable within a constant factor. We also show that the L-reducibility, the most widely used reducibility so far, has very bad closure properties: it does not preserve constant factor approximability. These negative results are proved under complexity-theoretic assumptions. We propose a new reducibility (the AP-reducibility) that overcomes all the limitations of previous definitions, and we prove several completeness results using the AP-reducibility. By making use of the PTAS-reducibility (a generalization of the AP-reducibility) we show how to improve the running time of approximation schemes for ``planar'' restriction of satisfiability problems.
We then turn to the problem of finding approximation-preserving reductions. Our emphasis here is on explicit non-approximability results. Our main result is a technique based on Linear Programming to find automatically approximation-preserving reductions by local replacement among a large class of problems, including Maximum Satisfiability, Maximum Cut, and problems expressing the computations of PCP verifiers. The reductions found by our method are optimal among local-replacement ones in terms of the way approximation is preserved. Our method works for several problems and yields the stronger known non-approximability results for Maximum Cut, Maximum Directed Cut and other related problems. It can also be used to find improved approximation algorithms.
The non-approximability results obtained in this way hold for the weighted versions of the studied problems. We show that for a large family of problems the unweighted version is precisely as hard to approximate as the weighted one. Finally, we present an improved non-approximability result for the Vertex Cover problem in bounded degree graphs.
1. Introduction ...................................... 1 1.1 History......................................... 3 1.2 The Results of This Thesis...................... 8 2. Background ........................................17 2.1 Optimization and Approximaiton..................17 2.2 Approximation-preserving Reducibilities.........19 2.3 PCP and the Hardness of Approximation...........22 2.4 Query Complexity................................23 2.5 Definition of the Problems......................24 3. Structure in Approximation Classes.................29 3.1 Reducibilities..................................30 3.2 Completeness....................................36 3.3 A PCP-free Completeness Result..................43 3.4 Query Complexity................................48 3.5 Applications to Natural Problems................52 3.6 Attributions and Related Works..................55 4. Tight Reductions ..................................57 4.1 Gadgets and Linear Programming..................58 4.2 Non-approximability Results Using Gadgets.......60 4.3 Approximation Algorithms Using Gadgets..........63 4.4 Lower Bounds for Gadgets COnstructions..........68 4.5 Removing Weights................................73 4.6 The Vertex Cover Problem........................80 4.7 Mixing Graphs, Mixing Sets, and Switchers.......84 4.8 Attributions and Related Works..................89 5. Conclusions and open Questions.....................91
