Advanced Algorithms Essay

140665 Words Jul 29th, 2013 563 Pages
Vijay V. Vazirani

College of Computing Georgia Institute of Technology

Copyright c 2001

Approximation Algorithms

Berlin Heidelberg NewYork Barcelona Hong Kong London Milan Paris Singapore Tokyo

To my parents


Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872–1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed conjecture that P = NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer
…show more content…
Part III covers four important topics. The first is the problem of finding a shortest vector in a lattice which, for several reasons, deserves individual treatment (see Chapter 27). The second topic is the approximability of counting, as opposed to optimization, problems (counting the number of solutions to a given instance). The counting versions of all known NP-complete problems are #Pcomplete1 . Interestingly enough, other than a handful of exceptions, this is true of problems in P as well. An impressive theory has been built for ob1

However, there is no theorem to this effect yet.



taining efficient approximate counting algorithms for this latter class of problems. Most of these algorithms are based on the Markov chain Monte Carlo (MCMC) method, a topic that deserves a book by itself and is therefore not treated here. In Chapter 28 we present combinatorial algorithms, not using the MCMC method, for two fundamental counting problems. The third topic is centered around recent breakthrough results, establishing hardness of approximation for many key problems, and giving new legitimacy to approximation algorithms as a deep theory. An overview of these results is presented in Chapter 29, assuming the main technical theorem, the PCP Theorem. The latter theorem, unfortunately, does not have a simple proof at present. The fourth topic consists of the numerous open

Related Documents