Seminar on Algorithms 0368-4210

Haim Kaplan, Spring 2023, Wednesdays 18-20, haimk@tau.ac.il

Shenkar 105

We will cover a few chapters from the book Beyond worst case analysis edited by Tim Roughgarden and some research papers mainly focused on online problems.

The most common method for analyzing algorithms is the so called worst case analysis where we bound the performance of the algorithm on its worst case input. Such an analysis often does not capture everything we want to know about the particular algorithm or problem.

Particularly, in the field of online algorithms, the common quality measure is the competitive ratio. This is the ratio between the cost of the algorithm and the smallest cost of the optimal offline algorithm that knows the entire input ahead of time – measured on the worst possible input. This measure is often hard to bound and does not distinguish well between the actual quality of different algorithms.

To mitigate this difficulty with worst case analysis, several different analysis techniques have been developed as well as different models for online algorithms. We will touch upon some of them.

Schedule

1) (Mar 15) An introductory lecture

2) (Mar 22) C. 2 - Parameterized Algorithms, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi, Roni Zehavi

3) (Mar 29) C. 3 - From Adaptive Analysis to Instance Optimality, Jérémy Barbay, Moria Nachmany

4) (April 19) C. 4 - Resource Augmentation, Tim Roughgarden, Amit Sandler

5) (May 5) C. 8 - Distributional Analysis, Tim Roughgarden, Yuval Shem-Tov

6) (May 17) C. 11 - Random-Order Models, Anupam Gupta, Sahil Singla, Alon Alexander

7) (June 14) C. 12 - Self-Improving Algorithms, C. Seshadhri, Inbal Hadad

8) (June 21) C. 15 - Smoothed Analysis of Pareto Curves in Multiobjective Optimization, Heiko Röglin, Tommy Winewtraub

9) (June 28 and Friday June 30) Correlation clustering and robust online correlation clustering, Omer Azoulay, Imri Efrat

10) (July 5) Online Steiner tree and generalized steiner tree (classical worst case model), Dean Oren

11) (Friday July 7) Online scheduling via learned weights, Nir Shalmon

12) (July 12) Learning from a sample in online algorithms (note the supplementary material), Ori Petel