Teaching

We teach algorithmic topics at the University of Zurich on a regular basis.

Randomized and Online Algorithms

ModuleBMINF014
ECTS6
InstructorP.D. Dr. Alexander Souza
Contact alexander@optineon.com
Lecture Noteshere
Exercise Sheetshere
Posterhere
Introductory Slideshere
RoomBIN-2.A.01
WeekdaysTuesday 8:15-9:45
Thursday 8:15-9:45
Exercisesbiweekly, see schedule below
Start20.2.2018
End31.5.2018
Exam12.6.2018
AdmissionHalf of the exercise problems must be worked on (serious attempt) for admission to the exam.
UZH Link here

News

Announcements concerning the course will be published here.

Description

This lecture covers the design and analysis of "randomized" as well as "online" algorithms.

A "randomized algorithm" is allowed to use randomness in its decision-making. In contrast, an "online algorithm" must make decisions "on the fly" before all of the information is available, and thus must be able to decide "under uncertainty."

The analysis will also be an important and integral part. That is, we will not only state the properties of an algorithm, e.g. its correctness or running time, but also prove them mathematically.

In particular, we plan to treat the following topics: Randomized Algorithms: Linearity of Expectation, Bounds on Probabilities, Probabilistic Method, and Randomized Rounding; with applications to Balls-Into-Bins, Quicksort, and Scheduling. Online Algorithms: Scheduling, List Update.

Schedule

Tue 20.02.20188:15-9:45Randomized Algorithms: Introduction
Thu 22.02.20188:15-9:45Randomized Algorithms: Introduction
Tue 27.02.20188:15-9:45Linearity of Expectation: Basics, Balls Into Bins
Thu 01.03.20188:15-9:45Linearity of Expectation: Coupon Collector
Tue 06.03.20188:15-9:45Linearity of Expectation: Quicksort
Thu 08.03.20188:15-9:45Exercise 1
Tue 13.03.20188:15-9:45Bounds on Probabilities: Basics, Markov, Chebyshev
Thu 15.03.20188:15-9:45Bounds on Probabilities: Generating Functions, Chernoff
Tue 20.03.20188:15-9:45Bounds on Probabilities: Balls Into Bins, Coupon Collector
Thu 22.03.20188:15-9:45Exercise 2
Tue 27.03.20188:15-9:45Bounds on Probabilities: Quicksort, Sampling with Replacement
Thu 29.03.20188:15-9:45Probabilistic Method
Tue 10.04.20188:15-9:45Randomized Rounding: Basics, Integer Linear Programs
Thu 12.04.20188:15-9:45Exercise 3
Tue 17.04.20188:15-9:45Randomized Rounding: Set Cover
Thu 19.04.20188:15-9:45Randomized Rounding: Satisfiability
Tue 24.04.20188:15-9:45Randomized Rounding: Derandomization
Thu 26.04.20188:15-9:45Exercise 4
Tue 03.05.20188:15-9:45Randomized Rounding: Plant Location
Thu 08.05.20188:15-9:45Online Algorithms: Introduction
Tue 15.05.20188:15-9:45Online Algorithms: Introduction
Thu 17.05.20188:15-9:45Exercise 5
Tue 22.05.20188:15-9:45Online Scheduling: Load Balancing
Thu 24.05.20188:15-9:45Online Scheduling: Bin Packing
Thu 29.05.20188:15-9:45List Update
Tue 31.05.20188:15-9:45Question Session
Tue 12.06.20188:15-9:45Exam

Literature

Research

Scientific Contributions

Events

We take part in scientific events and contribute actively to the operations research community. If you want to meet us, note the following meetings:

12-16.6.201713th MAPSPSeon (Germany)
6-7.2.2017Gurobi Days Frankfurt (Germany)
8.-12.6.201512th MAPSPLa Roche-en-Ardenne (Belgium)

Publications

[S13] Approximation Algorithms for Generalized Plant Location
Mathematical Foundations of Computer Science (MFCS '13), 789 – 800, 2013
[HMS13] A Simple and Tight Analysis for Generalized Vector Packing
joint work with Matthias Hellwig, Carsten Moldenhauer, submitted
[AS13] Buffer overflow management with class segregation
joint with Kamal Al Bawani, Information Processing Letters, 113 (4), 145 – 150, 2013
[HS12] Approximation Algorithms for Generalized and Variable Sized Bin Covering
joint with Matthias Hellwig, 15th International Workshop on Approximation Algorithms (APPROX ' 12), 194 – 205, 2012
[NS12] Optimal Algorithms for Train Shunting and Relaxed List Update Problems
joint with Tim Nonner, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS '12), 97 – 107, 2012
[S12] Adversarial Models in Paging – Bridging the Gap between Theory and PracticeComputer Science - Research and Development, invited contribution, 27 (3), 197 – 205, 2012
[S12a] Models and Algorithms for Assignment ProblemsHU Berlin, Habilitationsschrift, 2012
[A+11] Balanced Interval Coloring
joint with Antonios Antoniadis, Falk Hüffner, Pascal Lenzner, and Carsten Moldenhauer, 28th Symposium on Theoretical Aspects of Computer Science (STACS '11), 531 - 542, 2011
[LSS11] Optimal File-Distribution in Heterogeneous and Asymmetric Storage Networks
joint with Tobias Langner and Christian Schindelhauer, 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '11), 368 - 381, 2011
[CNS10] SRPT is 1.86-Competitive for Completion Time Scheduling
joint with Christine Chung and Tim Nonner, 12th Symposium on Discrete Algorithms (SODA '10), 1373 - 1388, 2010
[HS10] Tradeoffs and Average-Case Equilibria in Selfish Routing
joint with Martin Hoefer, journal version of [HS 07+08], Transactions on Computing Theory, 2 (1), 2010
[GNS09] The Bell is Ringing in Speed-Scaled Multiprocessor Scheduling
joint with Gero Greiner and Tim Nonner, Symposium on Parallelism in Algorithms and Architectures (SPAA '09), 11-18, 2009
[AS09] Competitive Buffer Management with Stochastic Packet Arrivals
joint with Kamal Al-Bawani, 8th Symposium on Experimental Algorithms (SEA '09), 28 - 40, 2009
[NS09a] A 5/3-approximation algorithm for joint replenishment with deadlines
joint with Tim Nonner, 3rd Conference on Combinatorial Optimization and Applications (COCOA '09), 24 - 35, 2009
[NS09] Latency Constrained Data Aggregation in Chain Networks
joint with Tim Nonner, 5th Conference on Algorithmic Aspects in Information and Management (AAIM '09), 279 - 291, 2009
[SS09] On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis
joint with Axel Simroth, 15th International Computing and Combinatorics Conference (COCOON '09), 168 - 177, 2009
[HS08] The Influence of Link Restrictions in (Random) Selfish Routing
joint with Martin Hoefer, 1st Symposium on Algorithmic Game Theory (SAGT '08), 22 - 32, 2008
[HS07] Tradeoffs and Average-Case Equilibria in Selfish Routing
joint with Martin Hoefer, 15th European Symposium on Algorithms (ESA '07), 63 - 74, 2007
[RSS07] On an Online Spanning Tree Problem in Randomly Weighted Graphs
joint with Jan Remy and Angelika Steger, Combinatorics, Probability and Computing, 16, 127 - 144, 2007
[S06] Average Performance AnalysisETH Zurich, Doctoral Thesis, 2006
[PS06] On Adequate Performance Measures for Paging
joint with Konstantinos Panagiotou, 38th ACM Symposium on Theory of Computing (STOC '06), 487 - 496, 2006
[SS06] The Expected Competitive Ratio for Weighted Completion Time Scheduling
joint with Angelika Steger, journal version of [SS04], invited contribution, Theory of Computing Systems, 39:1, 2006, pages 121 - 136
[SS04] The Expected Competitive Ratio for Weighted Completion Time Scheduling
joint with Angelika Steger, 21th Symposium on Theoretical Aspects of Computer Science (STACS ' 04), LNCS 2996, pages 620 - 631, Springer Verlag
[S01] Algorithms for Channel Assignment TU Munich, Diploma Thesis, 2001