Online Optimization (MA5516)
Lecture

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. 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 such as, e.g., packing, scheduling, matching and routing questions. We will cover both classical results as well as current research.

Lectures: Prof. Dr. Nicole Megow
Tutorials: Dr. Marek Adamczyk
Credits: 5 ECTS

News

  • July 25, 2016: Second exam will be within Sep 19-23.
  • May 25, 2016: There will be oral exams July 13/18/19, 2016 and in September.
  • March 31, 2016: The first lecture will be on April 13. The tutorials start one week later.
  • To participate in the tutorial classes, please register on TUMonline (Exercises for Online Optimization [MA5516]).
  • Exam schedule is now available

Schedule

Exam

Schedule is available here pdf The exam takes place in the office 02.04.040

Lectures

Day Time Room Lecturer
Wed 8:30-10:00 00.09.022 Prof. Dr. Nicole Megow

Tutorial Classes

Day Time Room Lecturer
Wed 10:15-11:45 03.06.011 Dr. Marek Adamczyk

Lecture Notes

Day Topic Documents
Apr 13, 2016 Organization and introduction pdf, pdf
Apr 20, 2016 List accessing problem, potential function method, averaging over adversaries pdf
Apr 27, 2016 Paging, introduction randomized algorithms pdf
May 04, 2016 Yao's principle, two-player zero-sum game, lower bounds for randomized online algorithms pdf
May 11, 2016 Lower bound randomized paging, intro online scheduling, load balancing pdf
May 18, 2016 Load balancing: Slowfit on related (8-comp.) and unrelated (O(logm)-comp.) machines pdf
May 25, 2016 Load balancing: lower bounds and restricted assignment (Greedy (log m + 1)-comp.), total weighted completion time pdf
Jun 1, 2016 Total weighted completion time: preemptive and non-preemptive pdf
Jun 8, 2016 Online bipartite matching, RANKING algorithm Section 2 only 
Jun 15, 2016 Analysis of RANKING algorithm, intro online primal-dual framework, approximate complementary slackness  
Jun 22, 2016 Online primal-dual algorithms for the ski rental problem pdf
Jun 29, 2016 Online Dial-a-Ride pdf
Jul 6, 2016 Online Deadline Scheduling with Speed Augmentation pdf
Jul 13, 2016 Scheduling on a machine of varying speed  

Exercise Sheets

Day Name Documents
Apr 13, 2016 Exercise Sheet 1 pdf
Apr 27, 2016 Exercise Sheet 2 pdf
May 13, 2016 Exercise Sheet 3 pdf
May 25, 2016 Exercise Sheet 4 pdf
Jun 10, 2016 Exercise Sheet 5 pdf
Jun 22, 2016 Exercise Sheet 6 pdf

Literature

  • Online Algorithms and Competitive Analysis, Alan Borodin and Ran El-Yaniv, Cambridge University Press