Speaker
Prof.
Hartmann Alexander
(University of Oldenburg)
Description
We study the vertex-cover problem on Erdös-Reny random
graphs, where previously a phase transition at connectivity
c=e coinciding with an easy-hard transition of a branch-
and-bound algorithm in connection with the leave-removal
heuristic has been found. Hence, this algorithm works by
partially exploring the space of feasible configurations. In
this work, we consider an algorithm which has a completely
different 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.
Primary author
Prof.
Hartmann Alexander
(University of Oldenburg)
