Academics

Teaching

Combinatorial and Approximation Algorithms

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 treat the following topics: Introduction; Greedy Algorithms: Minimum Spanning Trees, Set Cover; Network Flows: Maximum Flow, Minimum Cost Flow, Assignment; Matchings: Blossom Algorithm; Linear Programming: Polyhedra, Simplex; Knapsack: Exact Algorithm, FPTAS; Bin Packing: Hardness, Heuristics, APTAS; Set Cover: Greedy, Primal-Dual, LP-Rounding; Makespan Scheduling: Identical Machines, Unrelated Machines; Satisfiability; LP-Rounding, Randimization, Derandomization.

Randomized and Online Algorithms

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 to treat the following topics: Introduction; Linearity of Expectation; Bounds on Probabilities; Markov Chains; Randomized Rounding; Probabilistic Method; Online Computation; Load Balancing; Bin Packing; List Update.

Research

Publications

[S13]	Approximation Algorithms for Generalized Plant Location Mathematical Foundations of Computer Science (MFCS '13), 789 – 800, 2013
[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

Contact Us

Algomia GmbH
Schachenallee 29
5000 Aarau
Switzerland

Dr. Alexander Souza alexander@algomia.com

+41 62 544 79 60

Imprint