Akademie

Lehre

Combinatorial and Approximation Algorithms

Kombinatorische und Approximations-Algorithmen

Diese Vorlesung behandelt zentrale und klassische Ergebnisse aus dem Bereich der kombinatorischen Optimierung. Insbesondere wird der Entwurf und die Analyse von "kombinatorischen" als auch "approximativen"-Algorithmen behandelt.
"Kombinatorische Algorithmen" sind exakte Methoden mit (meist) polynomialer Zeit Methoden, die oft auf dynamischer Programmierung, Graphen und linearen Programmen. "Approximationsalgorithmen" erzeugen (potentiell suboptimale) machbare Lösungen für (in der Regel NP-schwere) Rechenprobleme. Die Qualität dieser Lösungen wird durch den Vergleich mit einer optimalen Lösung bestimmt.
Die Analyse wird ein wichtiger und integraler Bestandteil sein. Das heißt, wir werden Eigenschaften eines Algorithmus, z. B. seine Korrektheit oder Laufzeit, nicht nur Laufzeit, sondern beweisen sie auch mathematisch.
Wir behandeln insbesondere die folgenden Themen: Einführung; Greedy-Algorithmen: Minimum Spanning Trees, Set Cover; Netzwerkflüsse: Maximum Flow, Minimum Cost Flow, Assignment; Matchings: Blossom-Algorithmus; Lineare Programmierung: Polyeder, Simplex; Knapsack: Exakter Algorithmus, FPTAS; Bin Packing: Härte, Heuristik, APTAS; Set Cover: Greedy, Primal-Dual, LP-Rounding; Makespan Scheduling: Identische Maschinen, Unrelated Machines; Satisfiability; LP-Rounding, Randomisierung, Derandomization.

Randomisierte Algorithmen

Diese Vorlesung behandelt den Entwurf und die Analyse von "randomisierten" Algorithmen. Ein "randomisierter Algorithmus" darf bei seiner Entscheidungsfindung Zufälligkeit verwenden.
Die Analyse wird ebenfalls ein wichtiger und integraler Bestandteil sein. Das heißt, wir werden die Eigenschaften eines Algorithmus, z. B. seine Korrektheit oder Laufzeit, nicht nur angeben, sondern auch mathematisch beweisen.
Insbesondere werden wir folgende Themen behandeln: Einführung; Linearität der Erwartung; Schranken für Wahrscheinlichkeiten; Markov-Ketten; Randomisiertes Runden; Probabilistische Methode

Forschung

Veröffentlichungen

[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

Kontakt

Algomia GmbH
Schachenallee 29
5000 Aarau
Schweiz

Dr. Alexander Souza alexander@algomia.com

+41 62 544 79 60

Impressum