Ferienakademie – Sarntal 2019

Ferienakademie 2019 im Sarntal

Moderne Algorithmik: Randomisiert, online, approximativ

Sarntal / Italien – Sonntag, 22. September bis Freitag, 4. Oktober 2019

 
Dieser Kurs vermittelt den Studierenden ein grundlegendes Verständnis für moderne Ansätze in der kombinatorischen Optimierung. Er ist für Studierende im ersten oder zweiten Studienjahr der Informatik, Mathematik oder verwandten Studienrichtungen gedacht und generell für alle, die Interesse an diesem Themenbereich haben.

Dozenten

Die Dozenten des Kurses sind Prof. Dr. Harald Räcke, Technische Universität München, und Prof. Dr. Rolf Wanka, Friedrich-Alexander-Universität Erlangen-Nürnberg.

Gruppenfoto

Gruppenfoto Ferienakademie 2019 Kurs1 oder als zip

Törggelen

Vortrag zum Törggelen als pdf

Vorträge

Für den Vortrag hat jeder Studierende 45 Minuten zur Verfügung. Vortragsstil und Hilfsmittel sind dabei weitgehend frei wählbar. Folgende Alternativen sind z.B. möglich:

  • schrittweise Entwicklung eines Algorithmus an einem Flipchart
  • Vorstellung eines Computerprogramms, das die entwickelte Methode verdeutlicht
  • Beamerpräsentation der Vortragsfolien (LaTeX Vorlagen finden Sie hier)

Die Sprache für den Vortrag ist Deutsch oder Englisch.

Sarntal

Zusätzliche Informationen zum Sarntal finden Sie z.B. hier.

Projekt

Unterschiedliche Heuristiken werden benutzt um schwere Probleme zu lösen.

  • Hier finden Sie das Arbeitsblatt zum Projekt als pdf.

Links zu den einzelnen Instanzen:

  1. Min Cut (Tobias J.) Vortrag
  2. Minimum Multicut (Subhasri M.)
    • N. Garg, V. V. Vazirani, M. Yannakakis,
      Approximate Max-Flow Min-(Multi)cut Theorems and Their Applications, pdf
      Proc. 25th ACM Symp. on Theory of Computing (STOC), pp 698-707, 1993.
      doi:10.1145/167088.167266
    • V. V. Vazirani,
      Approximation Algorithms, Chapters 18, 20pdf
      Springer 2001
      doi:10.1007/978-3-662-04565-7
    • D. P. Williamson, D. B. Shmoys,
      The Design of Approximation Algorithms, Chapter 8.3
      Cambridge University Press 2011
  3. Sparsest Cut (Tobias K.) Vortrag
    • Y. Aumann, Y. Rabani:
      An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm pdf
      SIAM J. Comput. 27, 1, 291-301, 1998.
      10.1137/S0097539794285983
    • V.V. Vazirani:
      Approximation Algorithms,
      Chapters 21.1-21.5 pdf
      Springer Verlag, Berlin, 2001.
      doi:10.1007/978-3-662-04565-7
    • D. P. Williamson, D. B. Shmoys,
      The Design of Approximation Algorithms, Chapter 15.1, 15.4
      Cambridge University Press 2011
  4. Gomory Hu Trees (Kerstin F.)
  5. Mimicking Networks (Christoph P.) Vortrag
    • R. Krauthgamer, I. Rika:
      Mimicking Networks and Succinct Representations of Terminal Cuts pdf
      Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp, 1789-1799, 2013.
      doi:10.1137/1.9781611973105.128
    • A. Khan, P. Raghavendra, P. Tetali, L. Vegh:
      On Mimicking Networks Representing Minimum Terminal Cuts pdf
      Information Processing Letters, 114(7), 365-371, 2012.
      doi:10.1016/j.ipl.2014.02.011 oder offiziell bei
      arXiv:1207.6371
    • T. Hagerup, J. Katajainen, N. Nishimura, P. Ragde:
      Characterizing multiterminal flow networks and computing flows in networks of small treewidth pdf
      Journal of Computer and System Sciences 57(3) 366-375, 1998.
      doi:10.1006/jcss.1998.1592
  6. Edge Sparsification (Marcial G.) Vortrag
    • A. Benczur, D. Karger:
      Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs pdf
      SIAM J. Comput. 44(2) 290-319, 2015.
      doi:10.1137/07070597
    • D. Karger:
      Random Sampling in Cut, Flow, and Network Design Problems pdf
      Proc. 26th ACM Symp. on Theory of Computing (STOC), pp 648-657, 1994.
      doi:10.1145/195058.195422
  7. Approximating Graphs by Trees (Magnus K.) Vortrag
    • H. Räcke:
      Minimizing Congestion in General Networks. pdf
      Proc. 43rd IEEE Symp. on Foundations of Computer Sciene (FOCS), pp. 43-52, 2002.
      doi:10.1109/SFCS.2002.1181881
    • M. Bienkowski, M. Korzeniowski, H. Räcke:
      A Practical Algorithm for Constructing Oblivious Routing Schemes, pdf
      In Proc. 15th ACM Symp. on Parallel Algorithms and Architectures (SPAA), 24-33, 2003.
      doi:10.1145/777412.777418
  8. Vertex sparsification (N.N.)
    • A. Moitra:
      Vertex Sparsification and Oblivious Reductions pdf
      SIAM J. Comput. 42, 6, 2400-2423, 2013.
      doi:10.1137/100787337
    • M. Charikar, T. Leighton, S. Li, A. Moitra:
      Vertex Sparsifiers and Abstract Rounding Algorithms. pdf
      Proc. 51st IEEE Symp. on Foundations of Computer Sciene (FOCS), 265-274, 2010.
      doi:10.1109/FOCS.2010.32
    • M. Englert, A. Gupta, R. Krauthgamer, H. Räcke, I. Talgam-Cohen, K. Talwar:
      Vertex Sparsifiers: New Results from Old Techniques pdf
      SIAM J. Comput. 43, 4, 1239-1262, 2014.
      doi:10.1137/130908440

  1. Fundamentals of Optimization Problems (Sebastian H.) Vortrag
    • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
      Complexity and Approximation – Combinatorial Optimization Problems and Their Approximability Problems,
      pp. 22-38 pdf, pp. 87-152 pdf
      Springer-Verlag: Berlin-Heidelberg-New York, 1999
    • J. Hromkovič:
      Algorithmics for Hard Problems – Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics,
      pp. 213-238 pdf
      Springer-Verlag: Berlin-Heidelberg-New York, 2001
    • R. Wanka:
      Approximationsalgorithmen – Eine Einführung,
      pp. 81-85 pdf
      B.G. Teubner Verlag: Wiesbaden, 2006
      doi:10.1007/978-3-8351-9067-2
  2. The Knapsack Problem (Stefan S.)
    • J. Hromkovič:
      Algorithmics for Hard Problems – Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics,
      pp. 238-248 pdf
      Springer-Verlag: Berlin-Heidelberg-New York, 2001
  3. Dynamic Programming for Counting the Number of Knapsack Solutions (N.N.)
    • M. Dyer:
      Approximate counting by dynamic programming,
      pp. 693-699 pdf
      in: Proc. 35th ACM Symp. on Theory of Computing (STOC), 2003.
      10.1145/780542.780643
    • P. Gopalan, A. Klivans, R. Meka, D. Stefankovic, S. Vempala, E. Vigoda:
      An FPTAS for #Knapsack and Related Counting Problems,
      pp. 817-826 pdf
      in: Proc. 52nd IEEE Symp. on Foundations of Computer Science (FOCS), 2011.
      doi:10.1109/FOCS.2011.32
  4. Particle Swarm Optimization (PSO) and Parameter Selection (Andrei S.)
    • M. Jiang, Y. P. Luo, S. Y. Yang:
      Particle Swarm Optimization – Stochastic Trajectory analysis and parameter seletion,
      pp. 179-198 pdf
      Swarm Intelligence – Focus on Ant and Particle Swarm Optimization, 2007.
      doi:10.5772/5104
    • For background information, also refer to:
      Sabine Helwig:
      Particle Swarms for Constrained Optimization.
      (full text is available here)
      Ph.D. Thesis, University of Erlangen-Nuremberg, 2010.
  5. Particle Swarm Optimization for Discrete Problems (PSO) (Max S.) Vortrag
    • M. Mühlenthaler, A. Raß, M. Schmitt, A. Siegling, R. Wanka:
      Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax
      pp. 13-24 pdf
      Conference on Foundations of Genetic Algorithms (FOGA) 2017.
      doi: 10.1145/3040718.3040721
  6. Evolutionary Algorithms for Minimum Spanning Trees (EA) (Felix R.) Vortrag
    • F. Neumann, I. Wegener:
      Randomized local search, evolutionary algorithms, and the minimum spanning tree problem,
      pp 32-40 pdf
      Theoretical Computer Science 378, 2007.
      doi:10.1016/j.tcs.2006.11.002
  7. The Satisfiability Problem: Random Walk and Derandomization (Stefan L.) Vortrag
    • U. Schöning:
      A probabilistic algorithm for k-SAT based on limited local search and restart,
      pp 615-623 pdf
      Algorithmica 32, 2002.
      Paper beim Autor
    • R. A. Moser, D. Scheder:
      A Full Derandomization of Schöning’s k-SAT Algorithm,
      pp. 245-251 pdf
      in: Proc. 43rd ACM Symp. on Theory of Computing (STOC), 2011.
      doi:10.1145/1993636.1993670
  8. Constructive Proof of the Lovasz Local Lemma (Alexander B.) Vortrag
    • H. Gebauer, R. A. Moser, D. Scheder, E. Welzl:
      The Lovasz Local Lemma and Satisfiability,
      pp. 30-54 pdf
      Efficient Algorithms – Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, 2009.
      doi:10.1007/978-3-642-03456-5_3
  9. Approximate Counting: The Number of Colorings (Marvin J.) Vortrag