Teaching

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

Combinatoral and Approximation Algorithms

ModuleBMINF019
ECTS6
InstructorDr. Alexander Souza
Contact alexander@optineon.com
Lecture Noteshere
Exercise Sheetshere
Introductory Slideshere
RoomBIN-2.A.10
WeekdaysTuesday 8:15-9:45
Thursday 8:15-9:45
Exercisesbiweekly, see schedule below
Start19.2.2019
End28.5.2019
Exam11.6.2019
AdmissionHalf of the exercise problems must be worked on (serious attempt) for admission to the exam.
UZH Link here

News

Description

This lecture covers central and classical results in the area of combinatorial optimization. In particular, the design and analysis of "combinatorial" as well as "approximation" algorithms are treated.

"Combinatorial algorithms" are exact and (mostly) polynomial-time methods, often based on dynamic programming, graphs, and linear programs.

"Approximation algorithms" produce (potentially sub-optimal) feasible solutions for (usually NP-hard) computational problems. The quality of these solutions is determined by comparison against an optimal solution.

The analysis will 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:
  1. Introduction
  2. Greedy Algorithms: Minimum Spanning Trees, Set Cover
  3. Network Flows: Maximum Flow, Minimum Cost Flow, Assignment
  4. Matchings: Blossom Algorithm
  5. Linear Programming: Polyhedra, Simplex
  6. Knapsack: Exact Algorithm, FPTAS
  7. Bin Packing: Hardness, Heuristics, APTAS
  8. Set Cover: Greedy, Primal-Dual, LP-Rounding
  9. Makespan Scheduling: Identical Machines, Unrelated Machines
  10. Satisfiability; LP-Rounding, Randimization, Derandomization

Schedule

Tue 19.02.20198:15-9:45Introduction
Thu 21.02.20198:15-9:45Greedy
Tue 26.02.20198:15-9:45Greedy
Thu 28.02.20198:15-9:45Greedy
Tue 05.03.20198:15-9:45Network Flows
Thu 07.03.20198:15-9:45Exercise 1
Tue 12.03.20198:15-9:45Network Flows
Thu 14.03.20198:15-9:45Network Flows
Tue 19.03.20198:15-9:45Matchings
Thu 21.03.20198:15-9:45Exercise 2
Tue 26.03.20198:15-9:45Matchings
Thu 28.03.20198:15-9:45Linear Programming
Tue 02.04.20198:15-9:45Knapsack
Thu 04.04.20198:15-9:45Exercise 3
Tue 09.04.20198:15-9:45Knapsack
Thu 11.04.20198:15-9:45Bin Packing
Tue 16.04.20198:15-9:45Bin Packing
Thu 18.04.20198:15-9:45Exercise 4
Tue 30.04.20198:15-9:45Set Cover
Thu 02.05.20198:15-9:45NO CLASS
Tue 07.05.20198:15-9:45Set Cover
Thu 09.05.20198:15-9:45Makespan Scheduling
Tue 14.05.20198:15-9:45Makespan Scheduling
Thu 16.05.20198:15-9:45Exercise 5
Tue 21.05.20198:15-9:45Satisfiability
Thu 23.05.20198:15-9:45Satisfiability
Tue 28.05.20198:15-9:45Satisfiability
Tue 11.06.20198:15-9:45Exam

Vertex Cover Challenge

The problem Vertex Cover is defined as follows:

Given a graph G = (V, E), find a smallest subset C of V, such that each edge of E has at least one end-vertex in C.
This is a classical NP-hard optimization problem.
The organization PACE (Parameterized Algorithms and Computational Experiments) conducts an implementation and experimentation challenge for this problem.
Website: here
Instances: here

Improving Grades

Students can improve their final grade of the course by one quarter step if the following condition is satisfied: Here is a file with valid vertex-cover sizes (thresholds) of the 100 instances of the challenge. Whoever manages to submit feasible solutions to at least 50 instances (via the online checker below), whose vertex-cover sizes are not larger than the given sizes qualifies for the bonus. There is no limit concerning running time. This is valid until 11.06.2019.

This offering is a bonus. It is possible to get a 6.0 for the course without participation in this challenge (by performance in the final exam). However, it is not possible to get a grade better than 6.0 in any case.

We have an online checker for evaluations of your solutions. Just enter your email and upload your solutions-file and receive a summary indicating instance, feasibility, and cover size. See here for an example submission. The input format is a csv-file with the rows: instance-name TAB v1 SPACE v2 SPACE ..., where v1, v2, denote the vertices of your solution for the respective instance.


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