Carousel greedy: A generalized greedy algorithm with applications in optimization. (September 2017)

• Record Type: Journal Article
• Authors: Cerrone, Carmine; Cerulli, Raffaele; Golden, Bruce
• Is Part Of: Computers & operations research. Volume 85(2017)
• Page Start: 97
• Page End: 112
• Publication Date: 2017-09
• Subjects: Metaheuristics -- Greedy algorithm -- Combinatorial optimization -- Minimum label spanning tree -- Vertex cover -- Independent set -- Iterated greedy -- Carousel greedy; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.03.016
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We present a new, generalized greedy algorithm for solving a class of optimization problems. Our primary focus is on optimizing the cardinality of a set. The approach, however, can be applied more generally, even to problems in statistics. The approach generates high-quality results, but is much faster than typical metaheuristics. Abstract: 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.