direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Online Optimization

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

News

Information slides: info-slides.pdf (PDF, 830,5 KB) 

Contact Information

function
name
room
office hours
email
lecturer
Dr. Yann Disser
MA 518
after the lectures

lecturer
Dr. Nicole Megow
MA 505
after the lectures

Schedule
Time
Monday
Tuesday
Wednesday
Thursday
Friday
08-10
10-12
 
Lecture
MA 544 
 
 
12-14
 
 
 
Lecture
MA 313 
14-16
   
 
 
16-18
 
 
 

Outline and Problem Sheets

  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 (PDF, 78,4 KB)
  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 (PDF, 75,1 KB)
  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 (PDF, 117,5 KB)
  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 (PDF, 74,6 KB)
  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 (PDF, 75,9 KB)
  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

Literature

  •  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. 
  • EpsteinLevinMarchetti-SpaccamelaMegowMestreSkutellaStougie: Universal Sequencing on an Unreliable Machine. SIAM J. Comput. (SIAMCOMP) 41(3):565-586 (2012)
  • Cynthia A. PhillipsClifford SteinEric TorngJoel 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)

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe