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.

Time: | Wednesday, 2-4pm |

Room: | Gerhard-Konow-Hörsaal, Lennéstr. 2 |

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

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]**Lecture 4**[pdf]- ln4-approximation for Steiner trees

**Lecture 5**[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]