Regensburg 2016 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

DY: Fachverband Dynamik und Statistische Physik

DY 44: Critical Phenomena and Phase Transitions

DY 44.7: Vortrag

Mittwoch, 9. März 2016, 17:00–17:15, H47

Phase Transitions of Disordered Traveling Salesperson Problems solved with Linear Programming and Cutting Planes — •Hendrik Schawe and Alexander K. Hartmann — Institut für Physik, Carl-von-Ossietzky Universität Oldenburg, Oldenburg (Germany)

The Traveling Salesperson problem asks for the shortest cyclic tour visiting a set of cities given their pairwise distances and belongs to the NP-hard complexity class, which means that typical instances are not solveable in polynomial-time (if P ≠ NP holds), i.e. it is hard. Though that does not mean, that there are not subsets of the problem which are typically easy to solve. To examine a transitions from an easy to a hard phase, we study an ensemble of random configurations of cities in an Euclidean plane, characterized by a parameter σ, which governs the strength of the randomness. The instances are treated using a linear programming approach with selected cutting planes. We observe several phase transitions from easy to hard phases, depending on the types of cutting planes used. These transition are related to physical properties of the shortest tours and analyzed using finite-size scaling techniques.