NDMI018 - Aproximační a online algoritmy

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

LS/Spring 2024 - Jiří Sgall
Tuesday 15:40, S8

The tutorials are led by Tung Anh Vu and take place on Tuesday 9:00 in S8.

First lecture takes place Tue Feb 20, 2024.

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 S307, Malostranské nám. 25

Topics covered

1. (Feb 20)

introduction, approximation ratio, examples from previous course
coloring 3-chromatic graphs by O(n^1/2) colors
definition: PTAS and FPTAS [WS 3, V8]
scheduling, greedy algorithm (LIST) [WS 2.3]

2. (Feb 27)

(F)PTAS for scheduling on identical machines [WS 3.2, V10]definition: pseudopolynomial algorithms, strong NP-hardness [WS 3, V8]
relation of strong NP-hardness and FPTAS
bin packing, FIRST FIT [WS 3.3, V9]
asymptotic PTAS for bin packing [WS 3.3, V9]

3. (March 5)

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]

4. (March 12)

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]

5. (March 19)

chromatic number, algoritm for coloring 3-chromatic graphs by O(n^1/4) colors [WS 6.5, WS 13.2]

6. (March 26)

online algorithms: paging - deterministic algorithms and lower bounds [BE 3]
paging - H_k lower bounds for randomized algorithms [BE 4]

7. (April 2)

paging - 2H_k-competitive randomized algorithm [BE 4]
generalizations, weighted and file caching
k-server problem, definitions, overview of results [BE 10.1-10.4, BE 10.7]
k-server problem on a line and tree [BE 10.4]

8. (April 9)

k-server problem, lower bound in an arbitrary metric space [BE 10.1-10.3]
work function algorithm for k-server [BE 10.7, no proof]
online scheduling on identical machines

randomized 4/3-competitive algorithm for two machines [S]

9. (April 16)

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]

lower bounds for preemptive and nonpreemptive scheduling on related machines [ES1]

10. (April 23)

approximation of metric spaces by tree metrics [WS 8.5]

11. (April 30)

application of tree metrics: buy-at-bulk network design [WS 8.6]
online matching [EFFS]

12. (May 7)

PCP theorem and its applications, gap preserving reduction, examples [WS 16.3]

May 16 - no class, Rector's sports day
13. (May 21)

hardness of clique
unique games conjecture [WS 13.3, WS 16.5]

Topics covered during the last run in 2022

1. (Feb 21)

introduction, approximation ratio, examples from previous course
coloring 3-chromatic graphs by O(n^1/2) colors
definition: pseudopolynomial algorithms, strong NP-hardness [WS 3, V8]
definition: PTAS and FPTAS [WS 3, V8]

2. (Feb 28)

relation of strong NP-hardness and FPTAS
scheduling, greedy algorithm (LIST) [WS 2.3]
(F)PTAS for scheduling on identical machines [WS 3.2, V10]

3. (March 7)

bin packing, FIRST FIT [WS 3.3, V9]
asymptotic PTAS for bin packing [WS 3.3, V9]
shortest paths - Dijkstra's algorithm as a primal-dual one [WS 7.3]

4. (March 14)

generalized Steiner tree - 2-approximation by a primal-dual algorithm [WS 7.4]
semidefinite and vector programming [WS 6.1, V 26.1-26.3]

5. (March 21)

MAXCUT algorithm using semidefinite programming [WS 6.2, V 26.4-26.5]
chromatic number, algoritm for coloring 3-chromatic graphs by O(n^1/4) colors [WS 6.5, WS 13.2]

6. (March 28)

chromatic number, algoritm for coloring 3-chromatic graphs by O(n^1/4) colors [WS 6.5, WS 13.2]

7. (April 4)

approximation of metric spaces by tree metrics [WS 8.5]
application of tree metrics: buy-at-bulk network design [WS 8.6]

8. (April 11)

online algorithms: paging - deterministic algorithms and lower bounds [BE 3]
paging - 2H_k-competitive randomized algorithm [BE 4]
paging - H_k lower bounds for randomized algorithms [BE 4]
generalizations, weighted and file caching

April 18 - holiday, no class
9. (April 25)

k-server problem, definitions, overview of results [BE 10.1-10.4, BE 10.7]
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 algorithm for k-server [BE 10.7, no proof]

May 2 - spring school, no class
10. (May 9)

online matching [EFFS]
PCP theorem and its applications [WS 16.3]

May 16 - travel, no class
11. (May 23 - makeup class)

PCP theorem and its applications, gap preserving reduction, examples [WS 16.3]
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

[EFFS] Alon Eden, Michal Feldman, Amos Fiat, Kineret Segal:
An Economics-Based Analysis of RANKING for Online Bipartite Matching. SOSA 2021: 107-110.
Available as arXiv:1804.06637

[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