direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem

Maximilian Katzmann (FSU Jena)

 

We investigate the potential of exhaustively exploring larger neighborhoods in local search algorithms for Minimum Vertex Cover. More precisely, we study whether, for moderate values of k, it is feasible and worthwhile to determine, given a graph G with vertex cover C, if there is a k-swap S such that (C\ S)∪(S\ C) is a smaller vertex cover of G. First, we describe an algorithm running in ∆^O(k) · n time for searching the k-swap neighborhood on n-vertex graphs with maximum degree ∆. Then, we demonstrate that, by devising additional pruning rules that decrease the size of the search space, this algorithm can be implemented so that it solves the problem quickly for k ≈ 20. Finally, we show that it is worthwhile to consider moderately-sized k-swap neighborhoods. For our benchmark data set, we show that when combining our algorithm with a hill-climbing approach, the solution quality improves quickly with the radius k of the local search neighborhood and that in most cases optimal solutions can be found by setting k=21.

 

Date
Speaker
Location
Language
19.01.2017
16:15
Maximilian Katzmann
TEL 512
English

Back to the research colloquium site.

Zusatzinformationen / Extras