nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.08.2016

Multi-start iterated tabu search for the minimum weight vertex cover problem

verfasst von: Taoqing Zhou, Zhipeng Lü, Yang Wang, Junwen Ding, Bo Peng

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The minimum weight vertex cover problem (MWVCP) is one of the most popular combinatorial optimization problems with various real-world applications. Given an undirected graph where each vertex is weighted, the MWVCP is to find a subset of the vertices which cover all edges of the graph and has a minimum total weight of these vertices. In this paper, we propose a multi-start iterated tabu search algorithm (MS-ITS) to tackle MWVCP. By incorporating an effective tabu search method, MS-ITS exhibits several distinguishing features, including a novel neighborhood construction procedure and a fast evaluation strategy. Extensive experiments on the set of public benchmark instances show that the proposed heuristic is very competitive with the state-of-the-art algorithms in the literature.

Vorheriger Artikel Euclidean movement minimization

Nächster Artikel Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Balachandar SR, Kannan K (2009) A meta-heuristic algorithm for vertex covering problem based on gravity. Int J Math Stat Sci 1(3):130–136

Bouamama S, Blum C, Boukerram A (2012) A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Appl Soft Comput 12(6):1632–1639CrossRef

Chen J, Kanj IA, Xia G (2006) Improved parameterized upper bounds for vertex cover. Math Found Comput Sci 2006:238–249MathSciNetMATH

Chvatal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4(3):233–235MathSciNetCrossRefMATH

El Ouali M, Fohlin H, Srivastav A (2014) An approximation algorithm for the partial vertex cover problem in hypergraphs. J Comb Optim 28:1–19MathSciNetCrossRefMATH

Fu Z, Huang W, Lü Z (2013) Iterated tabu search for the circular open dimension problem. Eur J Oper Res 225(2):236–243MathSciNetCrossRefMATH

Glover F (1989) Tabu search-part i. ORSA J Comput 1(3):190–206CrossRefMATH

Huang W, Fu Z, Xu R (2013) Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container. Sci China Info Sci 56(9):1–14CrossRef

Jovanovic R, Tuba M (2011) An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Appl Soft Comput 11(8):5360–5366CrossRef

Karp RM, Miller RE, Theater JW (1972) Complexity of computer computations. Plenum Press, New York

Lü Z, Hao JK (2010) Adaptive tabu search for course timetabling. Eur J Oper Res 200(1):235–244CrossRefMATH

Lü Z, Huang W (2009) Iterated tabu search for identifying community structure in complex networks. Phys Rev E 80(2):026130CrossRef

Malek M, Guruswamy M, Pandya M, Owens H (1989) Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Ann Oper Res 21(1):59–84MathSciNetCrossRefMATH

Niedermeier R, Rossmanith P (2003) On efficient fixed-parameter algorithms for weighted vertex cover. J Algorithms 47(2):63–77MathSciNetCrossRefMATH

Peng B, Lü Z, Cheng T (2015) A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers Oper Res 53:154–164MathSciNetCrossRef

Shyu SJ, Yin PY, Lin BM (2004) An ant colony optimization algorithm for the minimum weight vertex cover problem. Ann Oper Res 131(1–4):283–304MathSciNetCrossRefMATH

Singh A, Gupta AK (2006) A hybrid heuristic for the minimum weight vertex cover problem. Asia Pac J Oper Res 23(02):273–285MathSciNetCrossRefMATH

Voß S, Fink A (2012) A hybridized tabu search approach for the minimum weight vertex cover problem. J Heuristics 18(6):869–876CrossRef

Zhang W, Wu W, Lee W, Du DZ (2012) Complexity and approximation of the connected set-cover problem. J Glob Optim 53(3):563–572MathSciNetCrossRefMATH

Zhang Z, Wu W, Fan L, Du DZ (2013) Minimum vertex cover in ball graphs through local search. J Glob Optim 59:1–9MathSciNetMATH

Titel: Multi-start iterated tabu search for the minimum weight vertex cover problem
verfasst von: Taoqing Zhou
Zhipeng Lü
Yang Wang
Junwen Ding
Bo Peng
Publikationsdatum: 01.08.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9909-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2016

Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

Optimal space coverage with white convex polygons

An -time exact algorithm for maximum -packing in cubic graphs

Euclidean movement minimization

A note on the duality between matchings and vertex covers in balanced hypergraphs

A hybrid algorithm based on variable neighbourhood for the strip packing problem