# Teaching

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

# Combinatoral and Approximation Algorithms

 Module BMINF019 ECTS 6 Instructor Dr. Alexander Souza Contact alexander@algomia.com Lecture Notes here Exercise Sheets here Introductory Slides here Room BIN-2.A.10 Weekdays Tuesday 8:15-9:45 Thursday 8:15-9:45 Exercises biweekly, see schedule below Start 19.2.2019 End 28.5.2019 Exam 11.6.2019 Admission Half of the exercise problems must be worked on (serious attempt) for admission to the exam. UZH Link here

## News

• We have a new room: BIN-2.A.10
• The exercise sheets are published
• NO CLASS on 2.5.; the class-schedule is updated
• Information on the Vertex Cover Challenge and grade improvement is available below
• Exercise 3 is postponed to 11.4. - Thus there is lecture on 4.4.

## 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.2019 8:15-9:45 Introduction Thu 21.02.2019 8:15-9:45 Greedy Tue 26.02.2019 8:15-9:45 Greedy Thu 28.02.2019 8:15-9:45 Greedy Tue 05.03.2019 8:15-9:45 Network Flows Thu 07.03.2019 8:15-9:45 Exercise 1 Tue 12.03.2019 8:15-9:45 Network Flows Thu 14.03.2019 8:15-9:45 Network Flows Tue 19.03.2019 8:15-9:45 Matchings Thu 21.03.2019 8:15-9:45 Exercise 2 Tue 26.03.2019 8:15-9:45 Matchings Thu 28.03.2019 8:15-9:45 Linear Programming Tue 02.04.2019 8:15-9:45 Knapsack Thu 04.04.2019 8:15-9:45 Knapsack Tue 09.04.2019 8:15-9:45 Bin Packing Thu 11.04.2019 8:15-9:45 Exercise 3 Tue 16.04.2019 8:15-9:45 Bin Packing Thu 18.04.2019 8:15-9:45 Exercise 4 Tue 30.04.2019 8:15-9:45 Set Cover Thu 02.05.2019 8:15-9:45 NO CLASS Tue 07.05.2019 8:15-9:45 Set Cover Thu 09.05.2019 8:15-9:45 Makespan Scheduling Tue 14.05.2019 8:15-9:45 Makespan Scheduling Thu 16.05.2019 8:15-9:45 Exercise 5 Tue 21.05.2019 8:15-9:45 Satisfiability Thu 23.05.2019 8:15-9:45 Satisfiability Tue 28.05.2019 8:15-9:45 Satisfiability Tue 11.06.2019 8:15-9:45 Exam

## 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

## Literature

• Cormen et al. – Introduction to Algorithms
• Korte, Vygen – Combinatorial Optimization
• Mitzenmacher, Upfal – Probability and Computing
• Vazirani – Approximation Algorithms

# 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.2017 13th MAPSP Seon (Germany) 6-7.2.2017 Gurobi Days Frankfurt (Germany) 8.-12.6.2015 12th MAPSP La 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 Packingjoint work with Matthias Hellwig, Carsten Moldenhauer, submitted [AS13] Buffer overflow management with class segregationjoint with Kamal Al Bawani, Information Processing Letters, 113 (4), 145 – 150, 2013 [HS12] Approximation Algorithms for Generalized and Variable Sized Bin Coveringjoint with Matthias Hellwig, 15th International Workshop on Approximation Algorithms (APPROX ' 12), 194 – 205, 2012 [NS12] Optimal Algorithms for Train Shunting and Relaxed List Update Problemsjoint 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 Coloringjoint 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 Networksjoint 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 Schedulingjoint 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 Schedulingjoint 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 Arrivalsjoint with Kamal Al-Bawani, 8th Symposium on Experimental Algorithms (SEA '09), 28 - 40, 2009 [NS09a] A 5/3-approximation algorithm for joint replenishment with deadlinesjoint with Tim Nonner, 3rd Conference on Combinatorial Optimization and Applications (COCOA '09), 24 - 35, 2009 [NS09] Latency Constrained Data Aggregation in Chain Networksjoint 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 Analysisjoint with Axel Simroth, 15th International Computing and Combinatorics Conference (COCOON '09), 168 - 177, 2009 [HS08] The Influence of Link Restrictions in (Random) Selfish Routingjoint with Martin Hoefer, 1st Symposium on Algorithmic Game Theory (SAGT '08), 22 - 32, 2008 [HS07] Tradeoffs and Average-Case Equilibria in Selfish Routingjoint with Martin Hoefer, 15th European Symposium on Algorithms (ESA '07), 63 - 74, 2007 [RSS07] On an Online Spanning Tree Problem in Randomly Weighted Graphsjoint 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