Phase transition for cutting-plane approach to vertex-cover problem
| Autor: | Dewenter, Timo, Hartmann, Alexander K. |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Zdroj: | Phys. Rev. E 86, 041128 (2012) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1103/PhysRevE.86.041128 |
| Popis: | We study the vertex-cover problem 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 replica symmetric to replica-symmetry broken. 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". 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. Comment: 4 pages, 3 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|