Logo Universität Erlangen-Nürnberg Logo TU München Logo Universität Stuttgart
Ferien-Akademie

Ferienakademie 2012, Course 2
Innovative Approaches to Combinatorial Optimization

Instructors

Guests:

Betreuer / Assistant:


(List of) Topics

We also plan to implement some of the heuristics (PSO, EA, Ants) and to test the implementations on common benchmarks.

The material can also be downloaded from this page, if the symbol appears (copyrighted material is password protected of course).

  • Optimization
    1. Fundamentals of Optimization Problems
      Dmitriy Serdyuk
      • 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, 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
        Springer-Verlag: Berlin-Heidelberg-New York, 2001
        pdf

      • R. Wanka:
        Approximationsalgorithmen - Eine Einführung, pp. 81-85
        B.G. Teubner Verlag: Wiesbaden, 2006
        pdf

    2. The Knapsack Problem
      Julia Grübel
      • J. Hromkovič:
        Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, pp. 238-248
        Springer-Verlag: Berlin-Heidelberg-New York, 2001
        pdf

    3. Dynamic Programming for Counting the Number of Knapsack Solutions
      Denis Aßmann
      • M. Dyer.
        Approximate counting by dynamic programming.
        in: Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 693-699, 2003.
        10.1145/780542.780643
        pdf

      • P. Gopalan, A. Klivans, R. Meka, D. Stefankovic, S. Vempala, E. Vigoda.
        An FPTAS for #Knapsack and Related Counting Problems.
        in: Proc. 52nd IEEE Symp. on Foundations of Computer Science (FOCS), pp. 817-826, 2011
        doi:10.1109/FOCS.2011.32
        pdf

    4. Blind Search
      unassigned
      • M. Dietzfelbinger, J. E. Rowe, I. Wegener, Ph. Woelfel:
        Tight Bounds for Blind Search on the Integers and the Reals.
        Combinatorics, Probability and Computing 19 (2010) 711-728.
        doi:10.1017/S0963548309990599
        pdf

    5. How far can't we go?
      Pavel Baikov
      • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
        Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Problems, pp. 175-286
        Springer-Verlag: Berlin-Heidelberg-New York, 1999
        pdf

      • J. Hromkovič:
        Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, pp. 281-302
        Springer-Verlag: Berlin-Heidelberg-New York, 2001
        pdf

    6. Particle Swarm Optimization (PSO) and Parameter Selection
      Manuel Schmitt
      • M. Jiang, Y. P. Luo, S. Y. Yang:
        Stochastic Convergence Analysis and Parameter Selection of the Standard Particle Swarm Optimization Algorithm.
        Information Processing Letters 102 (2007) 8-16.
        doi:10.1016/j.ipl.2006.10.005
        pdf

        For background information, also refer to:
        Sabine Helwig.
        Particle Swarms for Constrained Optimization.
        Ph.D. Thesis, University of Erlangen-Nuremberg, 2010. (full text is available here)

    7. Particle Swarm Optimization for Discrete Problems (PSO)
      unassigned
      • M. Clerc:
        Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem
        2000.
        Paper and source files

      • M. Hoffmann, M. Mühlenthaler, S. Helwig, R. Wanka:
        Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations.
        in: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS), pp. 416-427, 2011.
        doi:10.1007/978-3-642-23857-4_40
        pdf

    8. Particle Swarm Optimization Almost Surely Finds Local Optima
      Sonila Dobi
      • M. Schmitt, R. Wanka:
        Particle Swarm Optimization Almost Surely Finds Local Optima.
        Manuscript, 2012.
        pdf

    9. Evolutionary Algorithms for Sorting and Shortest Path Computation (EA)
      Alexander Rass
      • J. Scharnow, K. Tinnefeld, I. Wegener:
        The Analysis of Evolutionary Algorithms on Sorting and Shortest Paths Problems.
        Journal of Mathematical Modelling and Algorithms 3 (2004) 349-366.
        doi:10.1023/B:JMMA.0000049379.14872.f5
        pdf

    10. Evolutionary Algorithms for Minimum Spanning Trees (EA)
      Maxim Gladkikh
      • F. Neumann, I. Wegener:
        Randomized local search, evolutionary algorithms, and the minimum spanning tree problem.
        Theoretical Computer Science 378 (2007) 32-40.
        doi:10.1016/j.tcs.2006.11.002
        pdf

    11. Ant Systems for Minimum Spanning Trees (Ants)
      unassigned
      • F. Neumann, C. Witt:
        Ant Colony Optimization and the Minimum Spanning Tree Problem.
        in: Proc. Learning and Intelligent Optimization (LION), pp. 153-166, 2008.
        doi:10.1007/978-3-540-92695-5_12
        pdf

    12. The Satisfiability Problem: Random Walk and Derandomization
      Konstantin Chepurkin
      • U. Schöning.
        A probabilistic algorithm for k-SAT based on limited local search and restart.
        Algorithmica 32 (2002) 615-623.
        Paper beim Autor
        pdf

      • R. A. Moser, D. Scheder.
        A Full Derandomization of Schöning's k-SAT Algorithm.
        in: Proc. 43rd ACM Symp. on Theory of Computing (STOC), pp. 245-251, 2011.
        doi:10.1145/1993636.1993670
        pdf

    13. Randomized Optimization Algorithms
      Jannis Beese
      • D.S. Hochbaum:
        Approximation Algorithms for NP-hard Problems, pp. 447-459
        PWS Publishing Company: Boston, 1997
        pdf

      • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
        Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Problems, pp. 153-174
        Springer-Verlag: Berlin-Heidelberg-New York, 1999
        pdf

    14. Approaches based on the Primal-Dual Paradigm
      Ilya Chernyavsky
      • D.S. Hochbaum:
        Approximation Algorithms for NP-hard Problems, pp. 144-165
        PWS Publishing Company: Boston, 1997
        pdf