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