Article

Approximating covering problems by randomized search heuristics using multi-objective models

Authors:

Tobias Friedrich,

Nils Hebbinghaus,

Carsten WittAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 797 - 804

https://doi.org/10.1145/1276958.1277118

Published: 07 July 2007 Publication History

Abstract

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical ones on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare single-objective and multi-objective models for such problems. For the Vertex-Cover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case even no good approximation can be achieved within expected polynomial time. Examining the more general Set-Cover problem we show that optimal solutions can be approximated within a factor of log n, where n is the problem dimension, using the multi-objective approach while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.

References

[1]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2. edition, 2001.

Digital Library

[2]

R. Diestel. Graph Theory. Springer, 3rd edition, 2005.

[3]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci., 276:51--81, 2002.

Digital Library

[4]

O. Giel. Expected runtimes of a simple multi-objective evolutionary algorithm. In Proc. of CEC 2003, IEEE Press, pages 1918--1925, 2003.

[5]

O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem. In Proc. of STACS 2003, volume 2607 of LNCS, pages 415--426, 2003.

Digital Library

[6]

O. Glaser. Evolutionary algorithms and the vertex cover problem (in German). Department of Computer Science, University of Kiel, 2005.

[7]

J. He, X. Yao, and J. Li. A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem. IEEE Transactions on Systems, Man, and Cyber-netics, Part C, 35(2):266--271, 2005.

Digital Library

[8]

T. Jansen and I. Wegener. Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans. Evolutionary Computation, 5(6):589--599, 2001.

Digital Library

[9]

M. Laumanns, L. Thiele, and E. Zitzler. Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Trans. Evolutionary Computation, 8(2):170--182, 2004.

Digital Library

[10]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[11]

F. Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. In Proc. of PPSN 2004, volume 3242 of LNCS, pages 80--89, 2004.

[12]

F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In Proc. of GECCO 2004, volume 3102 of LNCS, pages 713--724, 2004.

[13]

F. Neumann and I. Wegener. Minimum Spanning Trees Made Easier Via Multi-Objective Optimization. Natural Computing, 5(3):305--319, 2006.

Digital Library

[14]

V. Vazirani. Appromixation Algorithms. Springer, 2001.

Digital Library

[15]

C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of STACS 2005, volume 3404 of LNCS, pages 44--56, 2005.

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
Yan XNeumann ANeumann F(2024)Sliding Window Bi-objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular FunctionsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_2(20-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_2
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 covering problems by randomized search heuristics using multi-objective models
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Approximating covering problems by randomized search heuristics using multi-objective models*

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical explorations on this subject. We consider ...
Multi-objective variable neighborhood search: an application to combinatorial optimization problems

Solutions to real-life optimization problems usually have to be evaluated considering multiple conflicting objectives. These kind of problems, known as multi-objective optimization problems, have been mainly solved in the past by using evolutionary ...
Runtime analysis of an evolutionary algorithm for stochastic multi-objective combinatorial optimization

For stochastic multi-objective combinatorial optimization (SMOCO) problems, the adaptive Pareto sampling (APS) framework has been proposed, which is based on sampling and on the solution of deterministic multi-objective subproblems. We show that when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
257
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 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
Yan XNeumann ANeumann F(2024)Sliding Window Bi-objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular FunctionsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_2(20-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_2
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
Branson LSutton AFinck SHellwig MOliveto P(2021)Focused jump-and-repair constraint handling for fixed-parameter tractable graph problemsProceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3450218.3477304(1-10)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1145/3450218.3477304
Chauhan AFriedrich TQuinzan FBosman P(2017)Approximating optimization problems using EAs on scale-free networksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071257(235-242)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071257
Pourhassan MShi FNeumann F(2016)Parameterized Analysis of Multi-objective Evolutionary Algorithms and the Weighted Vertex Cover ProblemParallel Problem Solving from Nature – PPSN XIV10.1007/978-3-319-45823-6_68(729-739)Online publication date: 31-Aug-2016
https://doi.org/10.1007/978-3-319-45823-6_68
Pourhassan MGao WNeumann FEsparcia-Alcázar A(2015)Maintaining 2-Approximations for the Dynamic Vertex Cover Problem Using Evolutionary AlgorithmsProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754700(903-910)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754700
Rohlfshagen PLehre PYao X(2013)Theoretical Advances in Evolutionary Dynamic OptimizationEvolutionary Computation for Dynamic Optimization Problems10.1007/978-3-642-38416-5_9(221-240)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38416-5_9
Qian CYu YZhou ZLanzi P(2011)An analysis on recombination in multi-objective evolutionary optimizationProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001852(2051-2058)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001852
Kaden LWeicker NWeicker KBeyer HLangdon W(2011)The role of selective pressure when solving symmetric functions in polynomial timeProceedings of the 11th workshop proceedings on Foundations of genetic algorithms10.1145/1967654.1967664(105-118)Online publication date: 5-Jan-2011
https://dl.acm.org/doi/10.1145/1967654.1967664
Show More Cited By

View Options

Get Access

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