Approximating vertex cover using edge-based representations

Thomas Jansen*, Pietro S. Oliveto, Christine Zarges

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

27 Citations (SciVal)

Abstract

In the literature only lower bounds are available on the approximation ratio of randomised search heuristics for vertex cover in the single-objective problem setting. These analyses are based on the natural vertex-based representation. Inspired by a well-known problem-specific approximation algorithm, we present an analysis of randomised search heuristics using edge-based representations. For the canonical objective function we prove that the performance can still be arbitrarily bad for the (1+1) EA and also RLS, even when using large search neighbourhoods. Adding slightly more information to the objective function turns RLS and the (1+1) EA into efficient 2-approximation algorithms requiring O(mlogm) steps where m is the number of edges. Although equivalent in the worst case, such an upper bound on the runtime is at least a linear factor better than that of the multi-objective case for sparse graphs and for graphs with large optimal vertex covers. Furthermore RLS algorithms, that after an improvement do not flip tested bits before trying previously untested ones, guarantee 2-approximations in O(m) steps.

Original languageEnglish
Title of host publicationFOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII
EditorsFrank Neumann, Kenneth De Jong
PublisherAssociation for Computing Machinery
Pages87-96
Number of pages10
ISBN (Print)9781450319904
DOIs
Publication statusPublished - 16 Jan 2013
Event12th ACM Workshop on Foundations of Genetic Algorithms, FOGA 2013 - Adelaide, SA, Australia
Duration: 16 Jan 201320 Jan 2013

Conference

Conference12th ACM Workshop on Foundations of Genetic Algorithms, FOGA 2013
Country/TerritoryAustralia
CityAdelaide, SA
Period16 Jan 201320 Jan 2013

Keywords

  • (1+1) EA
  • Random local search
  • Representation
  • Runtime analysis
  • Vertex cover

Fingerprint

Dive into the research topics of 'Approximating vertex cover using edge-based representations'. Together they form a unique fingerprint.

Cite this