Carousel greedy: A generalized greedy algorithm with applications in optimization

被引：45
作者：
Cerrone, Carmine [1 ]
Cerulli, Raffaele [2 ]
Golden, Bruce [3 ]
机构：
[1] Univ Molise, Dept Biosci & Terr, Molise, Italy
[2] Univ Salerno, Dept Math, Salerno, Italy
[3] Univ Maryland, Robert H Smith Sch Business, College Pk, MD 20742 USA
来源：
COMPUTERS & OPERATIONS RESEARCH | 2017年 / 85卷
关键词：
Metaheuristics Greedy algorithm; Combinatorial optimization; Minimum label spanning tree; Vertex cover; Independent set; Iterated greedy; Carousel greedy; VERTEX COVER; TABU SEARCH; HEURISTICS; SET;
D O I：
10.1016/j.cor.2017.03.016
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
In this paper, we introduce carousel greedy, an enhanced greedy algorithm which seeks to overcome the traditional weaknesses of greedy approaches. We have applied carousel greedy to a variety of well-known problems in combinatorial optimization such as the minimum label spanning tree problem, the minimum vertex cover problem, the maximum independent set problem, and the minimum weight vertex cover problem. In all cases, the results are very promising. Since carousel greedy is very fast, it can be used to solve very large problems. In addition, it can be combined with other approaches to create a powerful, new metaheuristic. Our goal in this paper is to motivate and explain the new approach and present extensive computational results. (C) 2017 Elsevier Ltd. All rights reserved.
引用
收藏
页码：97 / 112
页数：16
相关论文
共 38 条
  • [1] [Anonymous], 2013, Encyclopedia of Operations Research and Management Science, DOI DOI 10.1007/978-1-4419-1153-7
  • [2] [Anonymous], 1966, Applied regression analysis
  • [3] [Anonymous], 1996, American Mathematical Soc.
  • [4] Battiti R., 2015, LION WAY MACH LEARNI
  • [5] Metaheuristics in combinatorial optimization: Overview and conceptual comparison
    Blum, C
    Roli, A
    [J]. ACM COMPUTING SURVEYS, 2003, 35 (03) : 268 - 308
  • [6] A population-based iterated greedy algorithm for the minimum weight vertex cover problem
    Bouamama, Salim
    Blum, Christian
    Boukerram, Abdellah
    [J]. APPLIED SOFT COMPUTING, 2012, 12 (06) : 1632 - 1639
  • [7] A mixed integer linear formulation for the minimum label spanning tree problem
    Captivo, M. Eugenia
    Climaco, Joao C. N.
    Pascoal, Marta M. B.
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (11) : 3082 - 3085
  • [8] A Memetic Algorithm for the Weighted Feedback Vertex Set Problem
    Carrabs, Francesco
    Cerrone, Carmine
    Cerulli, Raffaele
    [J]. NETWORKS, 2014, 64 (04) : 339 - 356
  • [9] OMEGA one multi ethnic genetic approach
    Cerrone, Carmine
    Cerulli, Raffaele
    Gaudioso, Manlio
    [J]. OPTIMIZATION LETTERS, 2016, 10 (02) : 309 - 324
  • [10] Cerulli R, 2005, OPER RES COMPUT SCI, V29, P93
1234