Approximation and Online Algorithms

Monday 10:40, S8

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

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.

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

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

- 1. (Feb 27)
- introduction, approximation ratio, examples from previous course
- coloring 3-chromatic graphs by O(n
^{1/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(n
^{1/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(n
^{1/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]

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

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

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