A c-approximation algorithm is an efficient algorithm that produces feasible solutions for a given problem whose value is within a factor c of that of an optimum solution. A key step in designing good approximation algorithms is to find a high-quality bound on the value of an optimum solution. In this course, we will focus on bounds obtained through mathematical programming relaxations, and on how to round these into feasible solutions for the given problem.

Most of the topics to be discussed will be recent (i.e., from the past 5 years), and the course will therefore predominantly rely on research papers. Topics to be discussed will include:

• Advanced examples of iterative rounding (Steiner trees, Prize-Collecting Network Design)
• Graph decomposition methods and their application in polyhedral rounding
• Configurational LPs and how to round them (capacitated network design, minimum latency type problems)
• Lift & Project systems and their use in approximation algorithms
• Discrepancy rounding

Prerequisites: Combinatorial Optimization, in particular basic knowledge in graphs, linear programming, network flows, matching, and NP-completeness; see, e.g., Chapters 1-15 of the book by Korte and Vygen. Some familiarity with the basics of approximation algorithms (e.g., Chapter 16 of Korte & Vygen) may be useful.

Announcements

• The lecture of June 1 will be moved to May 30, 4-6pm, in the seminar room of the institute.
• The lecture of July 6 is cancelled.

Lecture Notes

Throughout the term, I will be posting handwritten lecture notes. The plan is to post the notes ahead of the lecture. Please let me know if you spot glaring errors, and I will do my best to correct.

• Lecture 1 [pdf]
  • Course information and overview
  • A generalization of Edmond's arborescence theorem due to Bang-Jensen, Frank and Jackson [pdf]
  • Applications to (Prize-Collecting) Steiner trees
• Lecture 2 [pdf]
  • Proving Bang-Jensen et al. via Frank's directed splitting-off result: On properties of Eulerian Digraphs, Annals of Discrete Mathematics,41 (1989)
• Lecture 3 [pdf]
  • Hypergraphic LPs for Steiner Trees
  • Byrka et al.'s Bridge Lemma (see [pdf])
  • Bounding the integrality gap of hypergraphic LPs; see also here for relatively easy (1+(ln 3)/2) bound on gap.
• Lecture 4 [pdf]
  • ln4-approximation for Steiner trees
• Lecture 5 [pdf]
  • Bidirected cut relaxation
  • See Appendix D of [arXiv], and also here: [pdf]
  • Improved results are here: [pdf]
• Lecture 6 [pdf]
  • Strong LP relaxations via flow-cover inequalities
  • [Carr, Fleischer, Leung, Pillips '00], [Carnes, Shmoys '08]
• Lecture 7 [pdf, pdf]
  • A framework for capacitated covering
  • [Chakrabarty, Grant, K. '10]
• Lecture 8 [pdf]
  • Solving set cover problems using geometric techniques
  • [Chan et al. '12], also: [Varadarajan'10], [Bansal, Pruhs'12]
• Lecture 9 [pdf]
  • Continue with geometric set-cover
• Lecture 10 [pdf]
  • LP-based approaches for capacitated facility location
  • [An, Singh, Svensson '14], [Abrams, Meyerson, Munagala, Plotkin '02]
• Lecture 11 & 12 [pdf]
• Continue our discussion of [An, Singh, Svensson '14] from last class
• Start discussing automatic strengthenings of LP relaxations; in particular, we will introduce the Lasserre lift-and-project hierarchy and discuss its use in approximation algorithms
  Our discussion follows the surveys [Rothvoss '13] and [Chlamtac & Tulsiani]