|Lectures:||Prof. Dr. Nicole Megow|
|Tutorials:||Dr. Marek Adamczyk|
- 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
ExamSchedule is available here The exam takes place in the office 02.04.040
|Wed||8:30-10:00||00.09.022||Prof. Dr. Nicole Megow|
|Wed||10:15-11:45||03.06.011||Dr. Marek Adamczyk|
|Apr 13, 2016||Organization and introduction||,|
|Apr 20, 2016||List accessing problem, potential function method, averaging over adversaries|
|Apr 27, 2016||Paging, introduction randomized algorithms|
|May 04, 2016||Yao's principle, two-player zero-sum game, lower bounds for randomized online algorithms|
|May 11, 2016||Lower bound randomized paging, intro online scheduling, load balancing|
|May 18, 2016||Load balancing: Slowfit on related (8-comp.) and unrelated (O(logm)-comp.) machines|
|May 25, 2016||Load balancing: lower bounds and restricted assignment (Greedy (log m + 1)-comp.), total weighted completion time|
|Jun 1, 2016||Total weighted completion time: preemptive and non-preemptive|
|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|
|Jun 29, 2016||Online Dial-a-Ride|
|Jul 6, 2016||Online Deadline Scheduling with Speed Augmentation|
|Jul 13, 2016||Scheduling on a machine of varying speed|
|Apr 13, 2016||Exercise Sheet 1|
|Apr 27, 2016||Exercise Sheet 2|
|May 13, 2016||Exercise Sheet 3|
|May 25, 2016||Exercise Sheet 4|
|Jun 10, 2016||Exercise Sheet 5|
|Jun 22, 2016||Exercise Sheet 6|
- Online Algorithms and Competitive Analysis, Alan Borodin and Ran El-Yaniv, Cambridge University Press