Statistische Mechanik kombinatorischer Optimierungsprobleme, Themenliste

1. Das Traveling Salesman Problem (TSP)
   • theoretical:
     O.C. Martin, R. Monasson, R. Zecchina
     Statistical mechanics methods and phase transitions in optimization problems
     Theoretical Computer Science 265, 3 (2001)
     
   • Stephan Mertens' Internet Sammlung
     http://odysseus.nat.uni-magdeburg.de/~mertens/TSP/index.html
2. Simulated Annealing
   • Kirkpatrick, S., C.D. Gelatt Jr, and M.P. Vecchi
     Optimization by Simulated Annealing
     Science 220, 671 (1983)
3. Phase transition in the satisfiability problem
   • R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky
     Nature 400, 133 (1999)
4. Generierung harter Instanzen für das Erfüllbarkeitsproblem
   • W. Barthel, A.K. Hartmann, M. Leone, F. Ricci-Tersenghi, M. Weigt, und R. Zecchina
     Generating hard and solvable satisfiability problems: A statistical mechanics approach
     Phys. Rev. Lett. 88, 188701 (2002)
   • W. Barthel
     Statistische Mechanik harter, lösbarer Erfüllbarkeitsprobleme
     Diplomarbeit, Göttingen, 2001
5. Zufallsgraphen und Perkolation
   • D. Stauffer und A. Aharony
     Perkolationstheorie - eine Einführung
     VCH, Weinheim 1995
   • P. Erdös and A. Rényi
     On radom graphs + The evolution of random graphs
     Magy. Tud. Akad. Mat. Fiz. Tud. Oszt. Kozl. 5, 17 (1960);
     in: The Art of Counting, edited by J. Spencer (MIT Press, Cambridge, MA, 1973)
6. Die "Äquivalenz" von Zufallsfeldsystemen und Netzwerken: schnelle maximale Fluß Algorithmen
   • J.C. Picard und H.D. Ratliff
     Minimum Cuts and Related problems
     Networks 5, 357 (1975)
   • A.K. Hartmann und U. Nowak
     Universality in three-dimensional random field systems
     Eur. Phys. J. B 7 , 105 (1999)
   • A. A. Middleton
     Critical Slowing Down in Polynomial Time Algorithms
     Phys. Rev. Lett. 88, 017202 (2002)
7. Computer-Complexität der Barrierenbewegung
   • A. A. Middleton
     Computational complexity of determining the barriers to interface motion in random systems
     Phys. Rev. E 59, 2571-2577 (1999)
8. Computer-Komplexität der Grundzustandsberechnung in Spingläsern
   • F. Barahona
     On the computational complexity of Ising spin glass models
     J. Phys. A 15, 3241 (1982)
   • M. Yannakakis
     Node- and Edge-Deletion NP-complete problems
     Proc. 10th Annual ACM Symp. on the Theory of Computing, Assosciation for Computing Machinery, New York, 253 (1978)
9. Algorithmen für Spinglas Grundzustandsberechnung und Komplexität
   • M. Jünger, G. Reinelt und S. Thienel
     Practical Problem Solving with cutting Plane Algorithms in Combinatorial Optimization
     Technischer Report No. 94.156, Universität Köln
   • F. Liers, M. Palassini, A.K. Hartmann und M. Jünger
     Critical zero-temperature behavior and computational complexity of diluted mean-field Ising spin glass
     preprint, in Vorbereitung
10. Das Zahlenaufteilungsproblem
    • S. Mertens
      A physicist's approach to number partitioning
      Theor. Comp. Science 265 79-108 (2001)
    • S. Mertens
      Phase transition in the number partitioning problem
      Phys. Rev. Lett 81 4281 (1998)
    • S. Mertens
      A complete anytime algorithm for balanced number partitioning
      preprint cs.DS/9903011

Allen Vortragenden wird empfohlen auch in der Datenbank INSPEC (nur lokal zugänglich) zu recherchieren. Eine sehr aktuelle Quelle stellt der Preprint-Server dar. Alle dort gespeicherten Artikel lassen sich direkt herunterladen. Allgemeine Informationen und Lehrbücher zu dem Thema finden sich unter:

• T.H. Cormen, S. Clifford, C. E. Leiserson, R. L. Rivest
  Introduction to Algorithms
  MIT Press 2001
• U. Schöning
  Theoretische Informatik - kurzgefasst
  Spektrum Akademischer Verlag, 1994
• A.V. Aho, J.E. Hopcroft, J.D. Ullman
  The design and analysis of computer algorithms
  Addison-Wesley 1974 (ebay!)
• M.R. Garey und D. S. Johnson
  Computers and intractability
  Freeman, New York, 1979
• C.H. Papadimitriou und K. Steiglitz
  Combinatorial Optimization
  Prentice-Hall 1982
• A.K. Hartmann und H. Rieger
  Optimization Algorithms in Physics
  Wiley-VCH, Berlin 2001