Analysis of an iterated local search algorithm for vertex cover in sparse random graphs

Publication: Research - peer-reviewJournal article – Annual report year: 2012

Standard

Analysis of an iterated local search algorithm for vertex cover in sparse random graphs. / Witt, Carsten.

In: Theoretical Computer Science, Vol. 425, 2012, p. 117-125.

Publication: Research - peer-reviewJournal article – Annual report year: 2012

Harvard

APA

CBE

MLA

Vancouver

Author

Witt, Carsten / Analysis of an iterated local search algorithm for vertex cover in sparse random graphs.

In: Theoretical Computer Science, Vol. 425, 2012, p. 117-125.

Publication: Research - peer-reviewJournal article – Annual report year: 2012

Bibtex

@article{a083de26382243929a10767ca9a1875a,
title = "Analysis of an iterated local search algorithm for vertex cover in sparse random graphs",
publisher = "Elsevier BV",
author = "Carsten Witt",
note = "This article is published in: {"}Special Issue on Theoretical Foundations of Evolutionary Computation{"} in the journal: {"}Theoretical Computer Science{"}",
year = "2012",
doi = "10.1016/j.tcs.2011.01.010",
volume = "425",
pages = "117--125",
journal = "Theoretical Computer Science",
issn = "0304-3975",

}

RIS

TY - JOUR

T1 - Analysis of an iterated local search algorithm for vertex cover in sparse random graphs

A1 - Witt,Carsten

AU - Witt,Carsten

PB - Elsevier BV

PY - 2012

Y1 - 2012

N2 - Recently, various randomized search heuristics have been studied for the solution of the minimum vertex cover problem, in particular for sparse random instances according to the G(n,c/n) model, where c>0 is a constant. Methods from statistical physics suggest that the problem is easy if c<e. This work starts with a rigorous explanation for this claim based on the refined analysis of the Karp–Sipser algorithm by Aronson et al. (1998) [1]. Subsequently, theoretical supplements are given to experimental studies of search heuristics on random graphs. For c<1, an iterated local search heuristic finds an optimal cover in polynomial time with a probability arbitrarily close to 1. This behavior relies on the absence of a giant component. As an additional insight into the randomized search, it is shown that the heuristic fails badly also on graphs consisting of a single tree component of maximum degree 3.

AB - Recently, various randomized search heuristics have been studied for the solution of the minimum vertex cover problem, in particular for sparse random instances according to the G(n,c/n) model, where c>0 is a constant. Methods from statistical physics suggest that the problem is easy if c<e. This work starts with a rigorous explanation for this claim based on the refined analysis of the Karp–Sipser algorithm by Aronson et al. (1998) [1]. Subsequently, theoretical supplements are given to experimental studies of search heuristics on random graphs. For c<1, an iterated local search heuristic finds an optimal cover in polynomial time with a probability arbitrarily close to 1. This behavior relies on the absence of a giant component. As an additional insight into the randomized search, it is shown that the heuristic fails badly also on graphs consisting of a single tree component of maximum degree 3.

KW - Randomized search heuristics

KW - Iterated local search

KW - Vertex cover

KW - Random graphs

KW - Karp–Sipser algorithm

KW - e-phenonemon

U2 - 10.1016/j.tcs.2011.01.010

DO - 10.1016/j.tcs.2011.01.010

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

VL - 425

SP - 117

EP - 125

ER -