February 25 – March 2 , 2001, Dagstuhl Seminar 01091

Algorithmic Techniques in Physics


Michael Jünger (Universität Köln, DE)
Gerhard Reinelt (Universität Heidelberg, DE)
Heiko Rieger (Universität des Saarlandes, DE)
Giovanni Rinaldi (IASI-CNR – Roma, IT)

For support, please contact

Dagstuhl Service Team


List of Participants
Dagstuhl-Seminar-Report 299


Nearly three years ago, in December 1997, the Dagstuhl Seminar "Algorithmic Techniques in Physics4 took place. Researchers from Computer Science, Mathematics and Physics came together to discuss about algorithmic problems occurring in physics and physical concepts that might be useful in computer science. Bringing together people from three different areas was an experiment that, as all participants agreed in the end, turned out to be a success and, more importantly, should be repeated in the future. This proposal is intended to initiate this repetition.

The original seminar was motivated by the observation that traditionally, there has always been a strong scientific interaction between physicists and mathematicians in developing physical theories. However, even though numerical computations are now commonplace in physics, no comparable interaction between physicists and computer scientists has been developed. Since the last three decades the design and the analysis of algorithms for decision and optimization problems evolved rapidly. Simultaneously, computational methods in theoretical physics became a major research tool causing a fast growing challenge with regards to the underlying algorithmic concepts. The few interactions between physicists and computer scientists were often successful and provided new insights in both fields. For example, in one direction, the algorithmic community has profited from the introduction of general purpose optimization tools like the simulated annealing technique that originated in the physics community. In the opposite direction, algorithms in linear, nonlinear, and discrete optimization have turned out to be useful tools in physics. Surprisingly often physicists and computer scientists are concerned with very similar questions but use a different terminology disguising in this way the significant overlap and preventing fruitful collaboration. Many notions of physicists in particle physics the computer scientists call problems or algorithms in combinatorics and external graph theory.

During the seminar it became clear that the communication that was intended by the organizers was indeed extremely fruitful. The computer scientists realized rather quickly that computational physicists often deal with very similar problems and try to solve them with a sometimes more pragmatic approach. And the physicists profited from the most recent algorithmic development that were useful for them but usually reach their community only decades later. Actually a number of participants (including the organizers) took home various ideas that were later converted into scientific publications. Various algorithms from combinatorial optimization are now standard tools in the computational physics community that studies the properties of ground states of disordered and complex systems. Some problems have been solved, but new ones have emerged. On the other hand, new algorithmic techniques have been developed which might be useful in solving these new problems. A selected list of topics that we intend to treat in this seminar is

  • Applications of polynomial optimization algorithms, including their problem specific implementation, to random physical systems. Well established examples here are the max-flow/min-cut algorithm to disordered ferromagnets or the min-cost-flow-algorithm to ensembles of magnetic flux lines.
  • Concrete physical realizations of various standard problems in combinatorial optimization.
  • New developments in heuristic algorithms for NP-hard physical problems, like the Coulomb- or the spin glass as well as new approaches to stochastic optimization (simulated annealing etc.)
  • The computational complexity of various compuationally hard physical problems as they occur in the physics of glassy systems.
  • Statistical properties and phase transitions of various standard problems in computer science like the K-sat problem with random inputs etc.
  • Scaling behavior of various geometric properties of standard algorithms applied to grid graphs.
  • And many more.

To summarize we think that in order that new results in optimization algorithms continue to reach the physics community and that interesting computational problems in physics come to the attention of the algorithmic designer it is a good time to repeat the successful seminar. We want to bring together the computer science, mathematical programming and physics communities in the pursuit of establishing new interactions and refreshing old ones, initiated in the `97 event.

Related Dagstuhl Seminar


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.