EWLS: A New Local Search for Minimum Vertex Cover

Keywords

Vertex cover, Edge cover, Iterated local search, Vertex (graph theory), Local optimum

References

• The Breakout Method for Escaping from Local MinimaPaul Morris — 1993
• A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a SphereStanislav Busygin, Sergiy Butenko, Pãnos M. Pardalos — 2002
• Some optimal inapproximability resultsJohan Håstad — 2001
• Handbook of Knowledge RepresentationPatrick Doherty, Jonas Kvarnström — 2008
• An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover ProblemShyong Jian Shyu, Peng-Yeng Yin, Bertrand M.T. Lin — 2004
• Improved approximation algorithms for the vertex cover problem in graphs and hypergraphsEran Halperin — 2000
• Reactive Local Search for the Maximum Clique Problem1Roberto Battiti, Marco Protasi — 2001
• Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique ProblemAndrea Grosso, Marco Locatelli, Federico Della Croce — 2004
• Random constraint satisfaction: Easy generation of hard (satisfiable) instancesKe Xu, Frédéric Boussemart, Fred Hémery — 2007
• Simple ingredients leading to very efficient heuristics for the maximum clique problemAndrea Grosso, Marco Locatelli, Wayne Pullan — 2008
• Solving the maximum clique problem by k-opt local searchKengo Katayama, Hamamoto Akihiro, Hiroyuki Narihisa — 2004
• A Novel Evolutionary Formulation of the Maximum Independent Set ProblemValmir C. Barbosa, Luciana C. D. Campos — 2003
• Clause Weighting Local Search for SATJohn Thornton — 2005
• A better approximation ratio for the vertex cover problemGeorge Karakostas — 2005
• Optimized Crossover for the Independent Set ProblemCharų C. Aggarwal, James B. Orlin, Ray P. Tai — 1997
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex coversWayne Pullan — 2009
• A study of ACO capabilities for solving the maximum clique problemChristine Solnon, Serge Fenet — 2006
• Clique is hard to approximate withinn1−εJohan Håstad — 1999
• Fast local search for the maximum independent set problemDiogo V. Andrade, Maurício G. C. Resende, Renato F. Werneck — 2008
• Dynamic Local Search for the Maximum Clique ProblemWayne Pullan, Holger H. Hoos — 2011

Cited by

• Unweighted Stochastic Local Search can be Effective for Random CSP BenchmarksChristopher D. Rosin — 2014
• Characterising fitness landscapes with fitness-probability cloud and its applications to algorithm configurationGuanzhou Lu — 2014
• Two New Local Search Strategies for Minimum Vertex CoverShaowei Cai, Kaile Su, Abdul Sattar — 2012
• Configuration Checking with Aspiration in Local Search for SATShaowei Cai, Kaile Su — 2012
• Adaptando Uma Solução GRASP ao Problema da Cobertura Mínima de VérticesMarco Antônio Barbosa, Igor Hoelscher, Fábio Favarim — 2013
• A clique-superposition model for social networksFei Yan, Shaowei Cai, Ming Zhang — 2012
• A review on algorithms for maximum clique problemsQinghua Wu, Jin‐Kao Hao — 2015
• Local search with edge weighting and configuration checking heuristics for minimum vertex coverShaowei Cai, Kaile Su, Abdul Sattar — 2011
• Local Search with Configuration Checking for SATShaowei Cai, Kaile Su — 2011
• More efficient two-mode stochastic local search for random 3-satisfiabilityChuan Luo, Kaile Su, Shaowei Cai — 2014
• Complete Boolean Satisfiability Solving Algorithms Based on Local SearchWensheng Guo, Guowu Yang, William N. N. Hung — 2013
• Local search for Boolean Satisfiability with configuration checking and subscoreShaowei Cai, Kaile Su — 2013
• Exact solutions to generalized vertex covering problems: a comparison of two modelsGary Kochenberger, Mark A. Lewis, Fred Glover — 2015
• NuMVC: An Efficient Local Search Algorithm for Minimum Vertex CoverShaowei Cai, Kaile Su, Chuan Luo — 2014
• Evolution of Social Networks: New Patterns and a New GeneratorFei Yan, Ming Zhang, Guojun Liu — 2011
• Backdoors to Tractable Answer-Set ProgrammingJohannes K. Fichte, Stefan Szeider — 2011
• The Impact of Max-SAT Resolution-Based Preprocessors on Local Search SolversFederico Heras, David Bañeres — 2010
• Two Weighting Local Search for Minimum Vertex CoverShaowei Cai, Jinkun Lin, Kaile Su — 2015
• A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problemRuizhi Li, Shuli Hu, Yiyuan Wang — 2016
• Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive GraphsShaowei Cai — 2015

Related papers

• Investigation of the traveling thief problemRogier Hans Wuijts, Dirk Thierens — 2019
• Local optima networks and the performance of iterated local searchFabio Daolio, Sebástien Vérel, Gabriela Ochoa — 2012
• To Combine or not to Combine Graybox Crossover and Local Search?Lorenzo Canonne, Bilel Derbel, Francisco Chicano — 2023
• Journey to the center of the linear ordering problemLeticia Hernando, Alexander Mendiburu, José A. Lozano — 2020
• An analysis of iterated local search for job-shop scheduling.L. Darrell Whitley, Adele E. Howe, Jean‐Paul Watson — 2003