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 3) C. 8 - Distributional Analysis, Tim Roughgarden, Yuval Shem-Tov

6) (May 10àFriday May 5) C. 11 - Random-Order Models, Anupam Gupta, Sahil Singla, Alon Alexander

7) (May 17) C. 12 - Self-Improving Algorithms, C. Seshadhri, Inbal Hadad

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

9) (May 31 and June 7) Correlation clustering and robust online correlation clustering, Omer Azoulay

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

11) (June 21) Online scheduling via learned weights, Nir Shalmon

12) (June 28) Learning from a sample in online algorithms (note the supplementary material), Dana Cohen