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