## NDMI018 - Aproximační a online algoritmy Approximation and Online Algorithms

### LS/Spring 2020 - Jiří Sgall Monday, 12:20, S9

CORONAVIRUS UPDATE: We have regular online classes, they are also recorded, see the links below

The language of the class will be English, the page will be converted gradually.

## Syllabus

For many optimization problems it is impossible to find an optimal solution fast. In such case, it is important to study approximation algorithms that work faster, but the solution they find is not necessarily an optimal one. Sometimes, we also have to react to partial input without knowledge of the complete input, by building a solution step by step. Such algorithms are called on-line. The subject of the course is the study of these two classes of algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and randomized algorithms.

## Contact info

E-mail: last name at iuuk.mff.cuni.cz
Phone: 951 554 293
http://iuuk.mff.cuni.cz/~sgall/
Office: 3rd floor, room 307, Malostranské nám. 25

## Covered topics

• 1. (Feb 27)
• introduction, approximation ratio, examples from previous course
• coloring 3-chromatic graphs by O(n1/2) colors
• scheduling, greedy algorithm (LIST) [WS 2.3]
• definition: pseudopolynomial algorithms, strong NP-hardness [WS 3, V8]
• definition: PTAS and FPTAS [WS 3, V8]
• 2. (March 2, by Martin Koutecký)
• shortest paths - Dijkstra's algorithm as a primal-dual one [WS 7.3]
• generalized Steiner tree - 2-approximation by a primal-dual algorithm [WS 7.4]
• 3. (March 9)
• (F)PTAS for scheduling on identical machines [WS 3.2, V10]
• bin packing, FIRST FIT [WS 3.3, V9]
• asymptotic PTAS for bin packing [WS 3.3, V9]
• -- (March 16 - recommended reading)
• semidefinite and vector programming [WS 6.1, V 26.1-26.3]
• MAXCUT algorithm using semidefinite programming [WS 6.2, V 26.4-26.5]
• chromatic number, algoritm for coloring 3-chromatic graphs by O(n1/4) colors [WS 6.5, WS 13.2]
• 4. (March 23 - recorded)
• MAXCUT algorithm using semidefinite programming - review [WS 6.2, V 26.4-26.5]
• chromatic number, algoritms for coloring 3-chromatic graphs [WS 6.5]
• 5. (March 30 - partially recorded)
• chromatic number, algoritm for coloring 3-chromatic graphs by O(n1/4) colors [WS 13.2]
• approximation of metric spaces by tree metrics - introduction [WS 8.5]
• 6. (April 6 - recorded)
• approximation of metric spaces by tree metrics [WS 8.5]
• 7. (April 20 - recorded)
• application of tree metrics: buy-at-bulk network design [WS 8.6]
• online algorithms: paging - deterministic algorithms and lower bounds [BE 3]
• 8. (April 27 - recorded)
• paging - 2H_k-competitive randomized algorithm [BE 4]
• paging - H_k lower bounds for randomized algorithms [BE 4]
• generalizations, weighted and file caching
• k-server problem, definitions, overview of results [BE 10.1-10.4, BE 10.7]
• 9. (May 4 - recorded)
• k-server problem on a line and tree [BE 10.4]
• k-server problem, lower bound in an arbitrary metric space [BE 10.1-10.3]
• work function algorithmus for k-server [BE 10.7, no proof]
• 10. (May 11 - recorded)
• online preemptive scheduling on uniformly related machines
• exact algorithm with known optimum [ES2]
• upper bounds for deterministic and randomized algorithms (doubling algorithms) [ES2]
• survey of results for nonpreemptive scheduling [S]
• 11. (May 18 - recorded)
• online preemptive scheduling on uniformly related machines
• lower bounds for preemptive and nonpreemptive scheduling on related machines [ES1]
• online matching [BM]
• 12. (May 25)
• online matching - recap
• PCP theorem and its applications, gap preserving reduction, examples  [WS 16.3]
• 12. (June 1)
• hardness of clique
• unique games conjecture [WS 13.3, WS 16.5]

## Study materials

For approximation algorithms the most up-to-date is the book by Williamson-Shmoys, I also recommend lecture notes by Williamson and the book by Vazirani. For onlines algorithm for paging and k-server I recommend the book by Borodin and El-Yaniv. For scheduling and online matching, I give pointers to some additional papers.

### Textbooks

[WS] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.
[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.
[BE] A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.
[FG] A. Fiat, G. Woeginger:  Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.

J. Hromkovic: Algorithmics for Hard Problems, Springer, 2001.
G. Ausiello et al: Complexity and Approximation, Springer, 1999.
D. S. Hochbaum (editor): Approximation algorithms for NP-hard problems, PWS publishing company, 1997. Papers

[BM] Benjamin Birnbaum and Claire Mathieu: On-line bipartite matching made simple
ACM SIGACT News, Volume 39 , Issue 1 (March 2008), pp. 80-87.

[S] J. Sgall: On-line scheduling
In Online Algorithms: The State of the Art, eds.A. Fiat and G. J. Woeginger, Lecture Notes in Comput. Sci. 1442, pages 196-231, Springer, 1998.

[ES1] L. Epstein, J. Sgall: A lower bound for on-line scheduling on uniformly related machines
Oper. Res. Lett., 26(1):17-22, 2000.

[ES2] T. Ebenlendr, J. Sgall: Optimal and online preemptive scheduling on uniformly related machines
In Proc. of the 21st Ann. Symp.  on Theor. Aspects of Comput. Sci. (STACS) , Lecture Notes in Comput. Sci. 2996, pages 199-210. Springer, 2004.

### Lecture notes (online)

David Williamson - a course on approximation algorithms: http://iuuk.mff.cuni.cz/~sgall/vyuka/dw-notes2.ps
Avrim Blum - a similar course: http://www-2.cs.cmu.edu/~avrim/Approx00/
Yossi Azar - a similar course: http://www.cs.tau.ac.il/~azar/online03.html

## Probraná látka podle přednášek v r. 2018

• 1. (27.2.)
• úvod, definice aproximačního poměru
• rozvrhování, hladový algoritmus (LIST) [WS 2.3]
• definice: pseudopolynomiální alg., silně NP-těžké úlohy [WS 3, V8]
• definice: PTAS a FPTAS [WS 3, V8]
• (F)PTAS pro rozvrhování na identických počítačích [WS 3.2, V10]
• 2. (6. 3.)
• bin packing, FIRST FIT [WS 3.3, V9]
• asymptotické PTAS pro bin packing [WS 3.3, V9]
• 3. (13. 3.)
• nejkratší cesta - Dijkstra jako primárně duální algoritmus [WS 7.3]
• zobecněný Steinerův strom - 2-aproximační primárně duální algoritmus [WS 7.4]
• 4. (20. 3.)
• semidefinitní a vektorové programování [WS 6.1, V 26.1-26.3]
• MAXCUT pomocí semidefinitního programování [WS 6.2, V 26.4-26.5]
• chromatické číslo, algoritmus pro obarvení 3-chromatických grafů O(n^1/4) barvami [WS 6.5 bez důkazu, WS 13.2]
• 5. (27. 3.)
• chromatické číslo, algoritmus pro obarvení 3-chromatických grafů O(n^1/4) barvami, dokončení
• aproximace metrik stromovými metrikami [WS 8.5]
• 6. (3. 4.)
• aproximace metrik stromovými metrikami, dokončení [WS 8.5]
• aplikace stromových metrik: buy-at-bulk network design [WS 8.6]
• 7. (10. 4.)
• problém paging, deterministické horní odhady [BE 3]
• pravděpodobnostní algoritmy pro paging, 2H_k horní odhad [BE 4]
• pravděpodobnostní algoritmy pro paging, H_k dolní odhad [BE 4]
• 8. (17. 4.)
• pravděpodobnostní algoritmy pro paging, dokončení
• k-server problém, definice, přehled výsledků [BE 10.1-10.4, BE 10.7]
• k-server problém, dolní odhad k v libovolném metrickém prostroru [BE 10.1-10.3]
• k-server problém na přímce [BE 10.4]
• k-server problém na stromech [BE 10.4]
• work function algoritmus pro k-server [BE 10.7 bez důkazu]
• 9. {24. 4.)
• online preemptivní rozvrhování na počítačích různých rychlostí
• přesný algoritmus se známým optimem [ES2] - probráno na cvičeních
• horní odhad pro deterministické  algoritmy (dvojnásobící algoritmy) [ES2]
• horní odhad pro pravděpodobnostní algoritmy (dvojnásobící algoritmy) [ES2]
• dolní odhad pro online rozvrhování na počítačích různých rychlostí (preemptivní i nepreemptivní) [ES1]
• online nepreemptivní rozvrhování na počítačích různých rychlostí - přehled výsledků [S]
• 10. (15. 5.)
• online párování - pravděpodobnostní algoritmus [BM]
• PCP věta a její použití, gap preserving redukce, příklady  [WS 16.3]
• 11. (22. 5.)
• dokazování neaproximace L-redukcemi [WS 16.2]
• unique games conjecture [WS 13.3, WS 16.5 bez důkazů]

Další plán podle předchozího běhu

• zatím vynechaná témata
• PTAS pro TSP v rovině [WS 10.1, V 11]
• 2-aproximační algoritmus  for scheduling on unrelated machines [V 17, WS 11.1]
• na cvičeních
• ski rental - deterministický a pravděpodobnostní algoritmus
• prohledávání přímky deterministicky