Algorithms and complexity

A.Y. 2020/2021
Overall hours
Learning objectives
Il corso consiste nella discussione di algoritmi di approssimazione per problemi NP-difficili; difficoltà di approssimazione dei problemi (in particolare, di alcuni affrontati nella prima parte); cenni della teoria della complessità di approssimazione (in particolare, il PCP); strutture dati succinte.
Expected learning outcomes
Course syllabus and organization

Single session

Lesson period
First semester
Synchronous video lessons.
Course syllabus
* Approximation algorithms

- The NPO, APX, PTAS, FPTAS complexity classes
- Greedy techniques
... The load balancing problem [A]
... The center selection problem [A]
... Inapproximability of the center selection problem [C]
... The set cover problem [A]
- Pricing technique
... The vertex cover probem [A]
... The disjoint paths problem [A]
- Rounding techniques
... Vertex cover by rounding [A]
- Other examples
... The Christofides algorithm for metric TSP [B]
... Inapproximability of TSP [D.6]
- Polynomial time and fully polynomial time approximation schemes
... A PTAS (based on the reduced exhaustive solution) of the minimum partition problem [G]
... A FPTAS (based on rounding) of the knapsack problem [C]

- Probabilistic algorithms

- The Karger algorithm for minimum global cut [E]
- The Miller-Rabin for primality (no proof) [H]
- A randomized-rounding algorithm for set cover [D.4]
- A probabilistic algorithm for MaxEkSat and its derandomization [D.3]
- Approximation complexity

- The PCP theorem (no proof) [F.3, Theorem 1]
- PCP and inapproximability of MaxSat and MaxE3Sat [F.3.1]
- PCP and inapproximability of independent set [F.4.4, Claim 13 and Claim 14]

- Succinct, quasi-succinct and compact data structures

- Succinct structures for rank and selection; the "Four-Russians Trick" [D.9, excluding 9.2]
- Succinct structures for binary trees [D.10]
- Quasi-succinct Elias-Fano coding for monotone sequences [D.11, excluding D.11.1 and D.11.2]
- Compact structure for balanced parenthesis [D.12]
- Quasi-succinct functions: the MWHC technique [D.13]
- Minimal perfect hashing [D.13]
Prerequisites for admission
Teaching methods
Frontal teaching.
Teaching Resources
[A] Chapter 11 (excluding 11.7) of Jon Kleinberg, Éva Tardos: Algorithm Design, Pearson, 2013
[B] Cornell handouts on the Christofides algorithm
[C] Kevin Wayne's slides
[D] Sebastiano Vigna's handouts
[E] Stanford slides on Karger's algorithm
[F] Luca Trevisan's handouts
[G] Section 3.2 of Ausiello et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer 1999
[H] Miller-Rabin's Algorithm (Wikipedia page)
Assessment methods and Criteria
Oral examination.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Boldi Paolo
Educational website(s)