Variable neighborhood search for the heaviest k-subgraph

被引：42

作者：

Brimberg, Jack ^{[2
]}

Mladenovic, Nenad ^{[3
]}

Urosevic, Dragan ^{[1
]}

Ngai, Eric ^{[4
]}

机构：

[1] Serbian Acad Sci, Math Inst, Belgrade, Serbia

[2] Royal Mil Coll Canada, Dept Business Adm, Kingston, ON, Canada

[3] Brunel Univ, Sch Math, Uxbridge UB8 3PH, Middx, England

[4] Hong Kong Polytech Univ, Dept Management & Mkt, Hong Kong, Hong Kong, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 11期

关键词：

Combinatorial optimization; Heaviest k-subgraph; Maximum diversity; Metaheuristics; Variable neighborhood search; TABU-SEARCH; GRASP;

D O I：

10.1016/j.cor.2008.12.020

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper presents a variable neighborhood search (VNS) heuristic for solving the heaviest k-subgraph problem. Different versions of the heuristic are examined including 'skewed' VNS and a combination of a constructive heuristic followed by VNS. Extensive computational experiments are performed on a series of large random graphs as well as several instances of the related maximum diversity problem taken from the literature. The results obtained by VNS were consistently the best over a number of other heuristics tested. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：2885 / 2891

页数：7

共 21 条

[1] [Anonymous], 1998, LNCS, DOI DOI 10.1007/BFB0053974
[2] Tabu Search versus GRASP for the maximum diversity problem
Aringhieri, Roberto
Cordone, Roberto
Melzani, Yari
[J]. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2008, 6 (01): : 45 - 60
[3] Obtaining test problems via Internet
Beasley, JE
[J]. JOURNAL OF GLOBAL OPTIMIZATION, 1996, 8 (04) : 429 - 433
[4] Billionnet A, 2005, INFOR, V43, P171
[5] Billionnet Alain, 2008, International Journal of Operational Research, V3, P301, DOI 10.1504/IJOR.2008.017534
[6] CLUSTERING AND DOMINATION IN PERFECT GRAPHS
CORNEIL, DG
PERL, Y
[J]. DISCRETE APPLIED MATHEMATICS, 1984, 9 (01) : 27 - 39
[7] Tabu search and GRASP for the maximum diversity problem
Duarte, Abraham
Marti, Rafael
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 178 (01) : 71 - 84
[8] THE DISCRETE PARA-DISPERSION PROBLEM
ERKUT, E
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 46 (01) : 48 - 60
[9] GALLEGO M, 2009, COMPUTATION IN PRESS, DOI DOI 10.1007/S10589-007-9161-6
[10] Computational aspects of the maximum diversity problem
Ghosh, JB
[J]. OPERATIONS RESEARCH LETTERS, 1996, 19 (04) : 175 - 181

← 1 2 3 →