Ferienakademie – Sarntal 2017

Ferienakademie 2017 im Sarntal

Moderne Algorithmik: Randomisiert, online, approximativ

Sarntal / Italien – Sonntag, 17. September bis Freitag, 29. September 2017

 
In diesem Kurs wird versucht, den Studierenden ein grundlegendes Verständnis für moderne Ansätze in der kombinatorischen Optimierung zu vermitteln. Der Kurs 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. Albers, Technische Universität München und Prof. Wanka, Friedrich-Alexander-Universität Erlangen-Nürnberg.
Der Kurs wird organisiert und betreut von Alexander Raß, Friedrich-Alexander-Universität Erlangen-Nürnberg.

Vorträge

Für den Vortrag hat jeder Studierende 90 Minuten (oder mehr) 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 und die Ausarbeitung ist vorzugsweise Englisch (oder Deutsch).

Ausarbeitung

  • Umfang ca. 10 Seiten
  • Inhalt: schriftliche Ausarbeitung des Vortrags (LaTeX Vorlagen finden Sie hier)
  • Abgabe bis spätestens 13. Oktober 2017

Vorbesprechungsfolien

Die Vorbesprechungsfolien von Prof. Albers finden Sie hier.

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:

Homepage-Image

Für den Fall, dass diese Homepage irgendwann vom Netz genommen wird, könnt ihr ein Abbild mit allen Wesentlichen Inhalten hier herunterladen.

Gruppenbild Ferienakademie 2017 Kurs1

  1. Selforganizing Data Structures (Philipp Scholl)
    Scholl
    Präsentation und Ausarbeitung
    • D.D. Sleator, R.E. Tarjan:
      Amortized efficiency of list update and paging rules,
      pp 202-208 pdf
      Commun. ACM, 28(2), 1985.
      doi:10.1145/2786.2793
    • N. Reingold, J. Westbrook, D.D. Sleator:
      Randomized competitive algorithms for the list update problem,
      pp 15-32 pdf
      Algorithmica 11(1), 1994.
      doi:10.1007/BF01294261
  2. Paging and Caching (Matthias Kammüller)
    Kammueller
    Präsentation und Ausarbeitung
  3. Scheduling: Makespan Minimization (Andreas Wilhelmer)
    Wilhelmer
    Präsentation und Ausarbeitung
    • V.V. Vazirani:
      Approximation Algorithms,
      pp 79-83 pdf
      Springer Verlag, Berlin, 2001.
      doi:10.1007/978-3-662-04565-7
    • L.A. Hall:
      Approximation algorithms for scheduling,
      Chapter 1, page 14 pdf
      In Approximation Algorithms for NP-hard Problems, edited by D.S. Hochbaum, PWS Publishing Co., 1996.
    • M. Englert, D. Özmen, M. Westermann:
      The power of reordering for online minimum makespan scheduling,
      pp 1220-1237 pdf
      SIAM J. Comput., 43(3), 2014.
      doi:10.1137/130919738
  4. Power Management (David Schneller)
    Schneller
    Präsentation und Ausarbeitung
    • S. Irani, S. K. Shukla, R. K. Gupta:
      Online strategies for dynamic power management in systems with multiple power-saving states,
      pp 325-346 pdf
      ACM Trans. Embedded Comput. Syst., 2(3), 2003.
      doi:10.1145/860176.860180
    • J. Augustine, S. Irani, and C. Swamy:
      Optimal power-down strategies,
      pp 1499-1516 pdf
      SIAM J. Comput., 37(5), 2008.
      doi:10.1137/05063787X
  5. Online Matching (Leander Schnaars)
    Schnaars
    Präsentation und Ausarbeitung
    • R.M. Karp, U.V. Vazirani, V.V. Vazirani:
      An optimal algorithm for on-line bipartite matching,
      pp 352-358 pdf
      Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990.
      doi:10.1145/100216.100262
    • B. Birnbaum, C. Mathieu:
      On-line bipartite matching made simple,
      pp 80-87 pdf
      SIGACT News, 39(1), 2008.
      doi:10.1145/1360443.1360462
    • A. Mehta, A. Saberi, U.V. Vazirani, V.V. Vazirani:
      AdWords and generalized online matching,
      pdf
      J. ACM, 54(5) 22, 2007.
      doi:10.1145/1284320.1284321
  6. Min-Cut (Katharina Hengel)
    Hengel
    Präsentation und Ausarbeitung
    • D.R. Karger, C. Stein:
      A New approach to the minimum cut problem,
      pp 601-640 pdf
      J. ACM 43(4), 1996.
      doi:10.1145/234533.234534
    • Material also in R. Motwani, P. Raghavan:
      Randomized Algorithms,
      pp 7-9 and 289-295 pdf
      Cambridge University Press, 1995.
    • M. Stoer, F. Wagner:
      A simple min-cut algorithm,
      pp 585 pdf
      Journal of the ACM. 44(4), 1997.
      doi:10.1145/263867.263872
  7. The Probabilistic Method (Felix Opolka)
    Opolka
    Präsentation und Ausarbeitung
    • M. Mitzenmacher, E. Upfal:
      Probability and Computing: Randomized Algorithms and Probabilistic Analysis,
      pp 126-134 pdf
      Cambridge University Press, 2005.
  8. Energy Conservation in Data Centers (Leo Fahrbach)
    Fahrbach
    Präsentation und Ausarbeitung
    • S. Albers:
      On energy conservation in data centers,
      pdf
      Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA17), 2017.
    • M. Lin, A.Wierman, L.L.H. Andrew, E. Thereska:
      Dynamic right-sizing for power-proportional data centers,
      pp 1378-1391 pdf
      IEEE/ACM Trans. Net., 21(5), 2013.
      doi:10.1109/TNET.2012.2226216
  9. Refined Input Models (nicht belegt)
    • S. Albers, D. Frascaria:
      Quantifying competitiveness in paging with locality of reference,
      pp 26-38 pdf
      Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP15), Springer LNCS 9134, 2015.
      doi:10.1007/978-3-662-47672-7_3
    • S. Albers, S. Lauer:
      On list update with locality of reference,
      pp 627-653 pdf
      J. Comput. Syst. Sci., 82(5): 2016.
      doi:10.1007/978-3-540-70575-8_9

  1. Fundamentals of Optimization Problems (Stefan Weißenberger)
    Weissenberger
    Präsentation und Ausarbeitung
    • 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 (Michael Loipführer)
    Loipfuehrer
    Präsentation und Ausarbeitung
    • 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 (Sabine Rieder)
    Rieder
    Präsentation und Ausarbeitung
    • 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 (Alexander Raß)
    • gnutzter Foliensatz von Manuel Schmitt als pdf
    • 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) (Florian Kronberger)
    Kronberger
    Präsentation und Ausarbeitung
    • 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 2017.
      doi: 10.1145/3040718.3040721
  6. Evolutionary Algorithms for Minimum Spanning Trees (EA) (Pascal Weickenmeier)
    Weickenmeier
    Präsentation und Ausarbeitung
    • 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 (Michael Jungmair)
    Jungmair
    Präsentation und Ausarbeitung
    • 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 (Christos Gazanis)
    Gazanis
    Ausarbeitung
    • 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 (Lukas Kamm)
    Kamm
    Präsentation und Ausarbeitung