Algorithmic Toolbox --- How to Solve Set Cover in x Ways

	Credits	2
	Lecturer	Ola Svensson
	Office hours	Wednesdays 14:00 - 16:00 in INJ 112
	Schedule	Mondays 14-16 in INM201.

Short description

The goal of this PhD course is to give PhD students a toolbox of algorithmic techniques in order to successfully address their favorite problems. The course emphases the illustration of the main ideas of these techniques. We prefer simplicity over details and we illustrate the algorithmic techniques in the simple and clean setting of the set cover problem. The algorithmic techniques that we plan to cover include

• Greedy algorithms
• Local search algorithms
• Linear programming
• Randomized rounding (independent, threshold, exponential clocks)
• Duality (primal-dual algorithms, dual fitting, and the use of complementarity slackness)
• Multiplicative weight update
• Online algorithms in adversarial and random order streams (primal-dual, potential function, and projection based)

In addition, to attending the lectures, students are required to submit a project report where they apply one of the algorithmic techniques in a more complex setting.

Schedule and references

• Lecture 1 (Monday February 27): Introduction. Greedy and Local Search Algorithms. References: Greedy algorithm, Local Search Algorithm (Section 2.1)
• Lecture 2 (Monday March 6): Linear programming, Threshold and Randomized rounding. References: LPs and Threshold Rounding, Independent Randomized Rounding, see also for a very nice analysis.
• Lecture 3 (Monday March 13): Exponential clocks, TU matrices, VC-dimension. References: Appendix A for exponential clocks, TU matrices and consecutive ones property , for VC-dimension see here and here
• Lecture 4 (Monday March 20):TU matrices, VC-dimension. References: Ola's notes
• Lecture 5 (Monday April 3):TU matrices References: Ola's notes on TU (last part) Sections 12.1, 13.1, and Exercise 14.1 in Vazirani's book
• Lecture 6 (Monday April 24):Duality: Chapter 15 in Vazirani's book. Multiplicative Weight Update: Lecture notes.
• Lecture 7 (Monday May 1): Multiplicative Weight Update: See notes from last time and also Section 3.4 in this survey. Introduction to online algorithms and primal-dual method,notes here and Chapter 4 in this book.
• Lecture 8 (Monday May 8): Online algorithms: Projection based (see first 7 pages here), potential notes (see notes by Anupam Gupta), random order (see Section 2 of this paper).
• Lecture 8 (Monday May 8): Online algorithms: random order (see Section 2 of this paper). Hardness of approximation: Chapter 29 of Vazirani's book. See also lectures in prior course here and here.

---