More Web Proxy on the site http://driver.im/

research-article

Approximating vertex cover using edge-based representations

Authors:

Pietro S. Oliveto,

Christine ZargesAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 87 - 96

https://doi.org/10.1145/2460239.2460248

Published: 16 January 2013 Publication History

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(m log m) 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.

References

[1]

T. Bäck and S. Khuri. An evolutionary heuristic for the maximum independent set problem. In Proceedings of the First IEEE International Conference on Evolutionary Computation (ICEC 1994), pages 531--535. IEEE Press, 1994.

[2]

N. Bansal and S. Khot. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming (ICALP 2010), LNCS 6198, pages 250--261. Springer, 2010.

Digital Library

[3]

T. N. Bui and P. H. Eppley. A hybrid genetic algorithm for the maximum clique problem. In Proceedings of the 6th International Conference on Genetic Algorithms (ICGA 1995), pages 478--484. Morgan Kaufmann, 1995.

Digital Library

[4]

I. Dinur and S. Safra. On the hardness of approximating vertex cover. Annals of Mathematics, 162(1):439--485, 2005.

[5]

B. Doerr, A. V. Eremeev, F. Neumann, M. Theile, and C. Thyssen. Evolutionary algorithms and dynamic programming. Theoretical Computer Science, 412(43):6020--6035, 2011.

Digital Library

[6]

B. Doerr, N. Hebbinghaus, and F. Neumann. Speeding up evolutionary algorithms through asymmetric mutation operators. Evolutionary Computation, 15(4):401--410, 2007.

Digital Library

[7]

B. Doerr, T. Jansen, and C. Klein. Comparing global and local mutations on bit strings. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), pages 929--936. ACM Press, 2008.

Digital Library

[8]

B. Doerr and D. Johannsen. Adjacency list matchings - an ideal genotype for cycle covers. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007), pages 1203--1210. ACM Press, 2007.

Digital Library

[9]

B. Doerr and D. Johannsen. Edge-based representation beats vertex-based representation in shortest path problems. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010), pages 759--766. ACM Press, 2010.

Digital Library

[10]

B. Doerr, C. Klein, and T. Storch. Faster evolutionary algorithms by superior graph representation. In Proceedings of the 1st IEEE Symposium on Foundations of Computational Intelligence (FOCI 2007), pages 245--250. IEEE Press, 2007.

[11]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1--2):51--81, 2002.

Digital Library

[12]

I. K. Evans. Evolutionary algorithms for vertex cover. In Proceedings of 7th International Conference on Evolutionary Programming (EP 1998), LNCS 1447, pages 377--386. Springer, 1998.

Digital Library

[13]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617--633, 2010.

Digital Library

[14]

T. Friedrich, P. S. Oliveto, D. Sudholt, and C. Witt. Analysis of diversity-preserving mechanisms for global exploration. Evolutionary Computation, 17(4):455--476, 2009.

Digital Library

[15]

O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), LNCS 2607, pages 415--426. Springer, 2003.

Digital Library

[16]

S. Guha, R. Hassin, S. Khuller, and E. Or. Capacitated vertex covering with applications. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pages 858--865. SIAM Press, 2002.

Digital Library

[17]

D. S. Hochbaum, editor. Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston, MA, USA, 1997.

Digital Library

[18]

T. Jansen, P. S. Oliveto, and C. Zarges. On the analysis of the immune-inspired B-cell algorithm for the vertex cover problem. In Proceedings of the 10th International Conference on Artificial Immune Systems (ICARIS 2011), LNCS 6825, pages 117--131. Springer, 2011.

Digital Library

[19]

G. Karakostas. A better approximation ratio for the vertex cover problem. ACM Transactions on Algorithms, 5(4):41:1--41:8, 2009.

Digital Library

[20]

S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pages 767--775. ACM Press, 2002.

Digital Library

[21]

S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. Journal of Computer and System Sciences, 74(3):335--349, 2008.

Digital Library

[22]

S. Khuri and T. Bäck. An evolutionary heuristic for the minimum vertex cover problem. In KI-94 Workshops (Extended Abstracts), pages 86--90. Gesellschaft für Informatik, 1994.

[23]

S. Kratsch and F. Neumann. Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65(4):754--771, 2013.

Digital Library

[24]

F. Neumann. Expected runtimes of evolutionary algorithms for the eulerian cycle problem. Computers & OR, 35(9):2750--2759, 2008.

Digital Library

[25]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[26]

P. S. Oliveto, J. He, and X. Yao. Time complexity of evolutionary algorithms for combinatorial optimization: a decade of results. International Journal of Automation and Computing, 4(3):281--293, 2007.

[27]

P. S. Oliveto, J. He, and X. Yao. Analysis of population-based evolutionary algorithms for the vertex cover problem. In Proceedings of the 10th IEEE Congress on Evolutionary Computation (CEC 2008), pages 1563--1570. IEEE Press, 2008.

[28]

P. S. Oliveto, J. He, and X. Yao. Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Transactions on Evolutionary Computation, 13(5):1006--1029, 2009.

Digital Library

[29]

C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982.

Digital Library

[30]

S. Pirzada and A. Dharwadker. Applications of graph theory. Journal of the Korean Society for Industrial and Applied Mathematics, 11(4):19--38, 2007.

[31]

F. Rothlauf. Representations for Genetic and Evolutionary Algorithms. Springer, 2006.

Digital Library

[32]

C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005), LNCS 3404, pages 44--56. Springer, 2005.

Digital Library

[33]

C. Witt. Analysis of an iterated local search algorithm for vertex cover in sparse random graphs. Theoretical Computer Science, 425(1):417--425, 2012.

Digital Library

Cited By

Lee JSutton A(2024)Evolving Populations of Solved Subgraphs with Crossover and Constraint RepairParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_9(133-148)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_9
Kearney JNeumann FSutton A(2023)Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex CoversProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607134(96-104)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607134
Branson LSutton A(2023)Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphsTheoretical Computer Science10.1016/j.tcs.2023.113719951(113719)Online publication date: Mar-2023
https://doi.org/10.1016/j.tcs.2023.113719
Show More Cited By

Index Terms

Approximating vertex cover using edge-based representations
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Fixed budget computations: a different perspective on run time analysis
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Randomised search heuristics are used in practice to solve difficult problems where no good problem-specific algorithm is known. They deliver a solution of acceptable quality in reasonable time in many cases. When theoretically analysing the performance ...
Performance analysis of randomised search heuristics operating with a fixed budget

When for a difficult real-world optimisation problem no good problem-specific algorithm is available often randomised search heuristics are used. They are hoped to deliver good solutions in acceptable time. The theoretical analysis usually concentrates ...
Analysis of the (1 + 1)-EA for finding approximate solutions to vertex cover problems

Vertex cover is one of the best known NP-Hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific ones. A theoretical analysis ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
147
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee JSutton A(2024)Evolving Populations of Solved Subgraphs with Crossover and Constraint RepairParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_9(133-148)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_9
Kearney JNeumann FSutton A(2023)Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex CoversProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607134(96-104)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607134
Branson LSutton A(2023)Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphsTheoretical Computer Science10.1016/j.tcs.2023.113719951(113719)Online publication date: Mar-2023
https://doi.org/10.1016/j.tcs.2023.113719
Baguley SFriedrich TKötzing TLi XPappik MZeif ZWagner M(2022)Analysis of a gray-box operator for vertex coverProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528848(1363-1371)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528848
Shi FYan XNeumann F(2022)Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling ProblemParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_37(526-541)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_37
Shastri HFrachtenberg E(2021)An analysis of the locality of binary representations in genetic and evolutionary algorithmsPeerJ Computer Science10.7717/peerj-cs.5617(e561)Online publication date: 25-May-2021
https://doi.org/10.7717/peerj-cs.561
Corus DOliveto PYazdani D(2021)Fast Immune System-Inspired Hypermutation Operators for Combinatorial OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.306857425:5(956-970)Online publication date: Oct-2021
https://doi.org/10.1109/TEVC.2021.3068574
Shi FNeumann FWang J(2021)Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problemTheoretical Computer Science10.1016/j.tcs.2021.09.003893(159-175)Online publication date: Nov-2021
https://doi.org/10.1016/j.tcs.2021.09.003
Doerr B(2020)The Runtime of the Compact Genetic Algorithm on Jump FunctionsAlgorithmica10.1007/s00453-020-00780-wOnline publication date: 13-Nov-2020
https://doi.org/10.1007/s00453-020-00780-w
Shi FNeumann FWang J(2020)Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover ProblemAlgorithmica10.1007/s00453-019-00662-wOnline publication date: 20-Jan-2020
https://doi.org/10.1007/s00453-019-00662-w
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents