Reductions and (Non-)Approximability

My PhD Thesis appeared in the following versions:

• Preliminary version (in English). November 1996. [Off-line]
  Was refereed by Mihir Bellare and Alessandro Panconesi. I defended it in January 1997 and it was accepted by the department.
  
• Official version (in Italian). February 1997. [Postscript]
  I defended this version on September 8, 1997, and it was accepted by a national committee appointed by the Ministry of University.
  
• Final version (in English). June 1997. [Postscript]
  Incorporates revisions suggested by the referees, and uses a more fancy LaTeX style file. It was printed as a booklet in a small number of copies. Send me an Email if you want to receive one of these hard copies.
  

My advisor is Pierluigi Crescenzi (now at the University of Florence).

Abstract

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 with 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 even 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.

The results of the thesis have been obtained in collaboration with Andrea Clementi, Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Gregory Sorkin, Madhu Sudan, and David Williamson. See also the list of my papers.