Online optimization is concerned with solving optimization problems when the input data is not fully available. The unknown parts of the data are revealed step by step and an online algorithm makes irrevocable decisions based only on the currently given information. An example is the elevator control in the math building of TU Berlin: Ideally, we want to minimize the waiting time of the users, but once a user requests an elevator, we immediately ("on-line") have to respond by sending one of the elevators without knowing any of the future requests. Can we design good algorithms for this problem? In this course, we will give an overview of fundamental techniques for the design and analysis of online algorithms for combinatorial optimization problems. We will cover both classical results as well as current research.

The course will be held either in English or German, depending on the audience. 

Leistungspunkte (ECTS): 10

Information slides: info-slides.pdf 

1. Lecture 14/10/2014: Introduction, online vs offline optimization, competitive ratio, ski-rental problem
2. Lecture 16/10/2014: List Accessing Problem, potential function method, averaging argument, tight bounds for move-to-front
3. Lecture 21/20/2014: List Accessing Problem cont., list-factoring technique for move-to-front, phase partitioning for Timestamp
4. Exercise 23/10/2014: problem sheet sheet1.pdf
5. Lecture 28/10/2014: Paging problem, LFD offline optimal, lower bound online deterministic paging algorithms
6. Lecture 30/10/2014: Marking algorithms, upper bound k, introduction randomized algorithms
7. Lecture 4/11/2014: Randomized Marking Alg. (RMARK) 2H_k-competitive, Yao's principle and lower bounds for online algorithms, two-player zero-sum games, simple ski rental lower bound
8. Lecture 6/11/2014: Randomized List Accessing
9. Exercise 11/11/2014: problem sheet sheet2.pdf
10. Lecture 18/11/2014: Lower bound H_k for randomized paging algorithms, Online load balancing, list scheduling
11. Lecture 20/11/2014: 8-competitive algorithm SlowFit for related machines, Greedy is (log m +1)-competitive for restricted assignment
12. Lecture 25/11/2014: Metrical Task Systems, lower bound via averaging, work function algorithm
13. Lecture 27/11/2014: k-server problem, lower bound for (h,k)-server (averaging), k-competitive algorithm for the line (potential function method) 
14. Lecture 2/12/2014: k-server problem for trees and graphs, 2-server problem for Euclidean spaces 
15. Lecutre 4/12/2014: balancing algorithm for the k-server problem on metric spaces of size k+1
16. Exercise 9/12/2014: problem sheet sheet3.pdf
17. Lecture 11/12/2014: Online scheduling min sum w_jC_j, fast single machine relaxation, preemptive Smith Rule, lower bound non-preemptive scheduling
18. Lecture 16/12/2014: convert preemptive to non-preemptive schedule, alpha-point scheduling
19. Lecture 18/12/2014: universal scheduling on an unreliable machine
20. Lecture 06/01/2015: online deadline scheduling with resource augmentation by higher speed, EDF and LLF are speed-(2-1/m) algorithms
21. Lecture 08/01/2015: general lower bound for speed req., augmentation by additional machines, non-preemptive setting, agreeable deadlines
22. Exercise 13/01/2015: problem sheet sheet4.pdf
23. Lecture 15/01/2015: online primal-dual algorithms, the ski-rental problem: deterministic and randomized
24. Lecture 20/01/2015: general online primal-dual framework for covering and packing problems, online set cover
25. Lecture 22/01/2015: online matching, primal-dual analysis for RANKING algorithm 
26. Exercise 27/01/2015: problem sheet sheet5.pdf
27. Lecture 29/01/2015: trading, deterministic search, randomized vs. deterministic trading, mixed trading strategy
28. Lecture 03/02/2015: treat based trading policy, matching lower bound
29. Lecture 05/02/2015: graph exploration, exploration in exponential time, combination locks, mapping with return-path oracle

•  Borodin, El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 2005. (main course material)
• Chekuri, Motwani, Natarajan, Stein: Approximation Techniques for Average Completion Time Scheduling. SIAM J. Comput. (SIAMCOMP) 31(1):146-166 (2001)
• Martin Skutella: List Scheduling in the oder of α-points, Efficient Approximation and Online Algorithms, LNCS 3484, pp 250-291, 2006. 
• Epstein, Levin, Marchetti-Spaccamela, Megow, Mestre, Skutella, Stougie: Universal Sequencing on an Unreliable Machine. SIAM J. Comput. (SIAMCOMP) 41(3):565-586 (2012)
• Cynthia A. Phillips, Clifford Stein, Eric Torng, Joel Wein: Optimal Time-Critical Scheduling via Resource Augmentation. Algorithmica 32(2):163-200 (2002)
• R. El-Yaniv, A. Fiat, R. M. Karp, G. Turpin: Optimal Search and One-Way Trading Online Algorithms. Algorithmica 30:101-139 (2001)
• Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil Vadhan: The Power of a Pebble: Exploring and Mapping Directed Graphs. Information and Computation 176(1):1-21 (2002)