AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

60 Minutes

Saarbrücken

The subject of the talk is located at the interface of computer
science and physics. In particular, the vertex-cover problem is
presented, which is an NP-hard optimization problem and a prototypical
model exhibiting phase transitions on random graphs, e.g.,
Erdoes-Renyi (ER) random graphs. These phase transitions coincide
with changes of the solution space structure, e.g, for the ER ensemble
at connectivity c=e=2.7183 from simple, with one large cluster of
solutions, to a complex hierarchically clustered landscape. For the
vertex-cover problem, also the typical complexity of exact
branch-and-bound algorithms, which proceed by exploring the landscape
of feasible configurations, change close to this phase transition
from ``easy'' to ``hard''. Most recently, we considered an algorithm
which has a completely different but for practical applications
standard algorithmic strategy: The problem is mapped onto a linear
programming problem augmented by a cutting-plane approach, hence the
algorithm operates in a space *outside* the space of feasible
configurations until the final step, where a solution is found. Here
we show that this type of algorithm also exhibits an easy-hard
transition around c=e, which strongly indicates that the typical
hardness of a problem is fundamental to the problem and not due to a
specific representation of the problem.

Literature:
* A.K. Hartmann and H. Rieger, Optimization Algorithms in Physics
(Wiley-VCH, Berlin 2001)
* A.K. Hartmann and H. Rieger (eds.), New Optimization Algorithms in Physics
(Wiley-VCH, Berlin 2004)
* A.K. Hartmann and M. Weigt, Phase Transitions in Combinatorial
Optimization Problems (Wiley-VCH, Berlin 2005)
* A.K. Hartmann, Practical Guide to Computer Simulations
(World Scientific, Singapore 2009)

Kurt Mehlhorn

--email hidden

passcode not visible

logged in users only