Google Scholar

Tuesday, June 20, 2006

READING LIST ON APPROXIMATION ALGORITHMS

  • Vijay Vazirani, Approximation Algorithms
    Well-written anc comprehensive approach to approximation algorithms from a classical point of view. The first part of the book provides approximation algorithms for many combinatorial NP-hard algorithms, and it is perhaps the best algorithm-oriented introduction into approximation algorithms. The second part of the book describes connections between approximation and LP (Logical Programming) by means of LP-relaxation or dual-schemas. Contains LP-based approximatioon algorithms for many combinatorial problems with proofs of upper bounds. The third part is a selection of topics. Only chapter 28 (counting problems) was interesting for me. Chapters 27(shortest vector) and 29 (hardness of approximation) are not in particular deep comparing to other books

  • Approximation Algorithm for NP-hard problems by Dorit Hochbaum is a set of chapters by different contributors. Perhaps, the best source on approximation algorithms. Contains an excellent chapter (Chapter 10) by Sanjeev Arora and Carsten Lund on hardness of approximation, which introduces 4 main approximation complexity classes for NP-hard problems and contains a small compendium of hard-problems for those classes with proofs of hardness of approximation. The chapter is available online at Arora's website. Recommended to read in conjunction with Hougardy's books chapter. (Arora's chapter does not contain proofs of in-approximability for class IV, see Hougarchy's chapter for that). Contains an exccelent chapter on approximation of counting problems by Monte Carlo method. Chapter 3 was in particular useful in my work since it is an excellent survey of algorithms and hardness resuls for Set Cover and Independent Set problems commonly met in inconsistent database theory. Chapter 9 by Hochbaum is an introduction into different classes of approximation by measure approximation factor & time. Basically it focus on constant-factor approximation (CLASS I according to chapter 10) and PTAS problems and described different efficient algorithms for them. Very good from practical points of view since it considers different techniques to get shorter times and better approximation factors for "practical" problems

  • Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties by Ausiello et al. A texbook which is good for undergraduate or non advanced graduate course. A chapter about probalistic analysis was in particular interesting for me, the others seem to be oversimplified.

  • Probabilistically checkable proofs and their consequences for approximation algorithms by Stefan Hougardy et al. In: Walter A. Deuber, Hans Jürgen Prömel und Bernd Voigt (Herausgeber): Trends in Discrete Mathematics, Seiten 175-223. North Holland.
    The first part of this chapter contains proof of in-approximation properties for the clique number (simple constant factor non-approximation and more involved proof n^\epsilon non-approximation which is a good introduction into hardness proofs for CLASS IV), chromatics number(simple proof by Khanna, Linial, Safra), and MAX-SNP hard problems (syntactic class introduced by Papadimitriou and Yannakakis, which contains many common combinatorial problems like MAX-SAT, MAX-CUT, EUCLIDIAN TSP)

  • Lecture notes on approximation algorithms by Prof. Michel Goemans, MIT. A very short introduction into hardness of approximation, then good introduction into LP-rounding techniques, analysis of algorithms and approximation algorithms for max-cut, bin packing problems. Recommended to understand the analysis of approximation algorithms.

  • Probabilistic Checking of Proofs and Hardness of Approximation Problems by Sanjeev Arora. For hatdness of approximation results, see chapter 6 . A comprehensive introduction into proof of hardness results. I would recommend to read after Arora, Lund chapter at Hochbaum book and Hougardy's chapter.

  • A comprehensive and up-to-date the compendium of NP optimization problems by Creszenzi and Kann which contains approximation-non-approximation results for optimization problems.