Authors: Brimberg, Jack
Mladenović, Nenad 
Todosijević, Raca 
Urošević, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Less is more: Solving the Max-Mean diversity problem with variable neighborhood search
Journal: Information Sciences
Volume: 382-383
First page: 179
Last page: 200
Issue Date: 1-Mar-2017
Rank: M21a
ISSN: 0020-0255
DOI: 10.1016/j.ins.2016.12.021
Within the broad class of diversity/dispersion problems we find an important variant known as the Max–Mean Diversity Problem, which requires finding a subset of a given set of elements in order to maximize the quotient of the sum of all edges belonging to that subset and the cardinality of the subset. In this paper we develop a new application of general variable neighborhood search for solving this problem. Extensive computational results show that our new heuristic significantly outperforms the current state-of-the-art heuristic. Moreover, the best known solutions have been improved on 58 out of 60 large test instances from the literature. In other words, despite the simplicity of our method, which is a desirable property for any heuristic, we achieve significantly better results than a more complex heuristic that represents the state-of-the-art. Thus, simplicity can lead to more efficient and effective methods: when heuristics are used, less can be more.
Keywords: Diversity/dispersion problem | Maximum-mean | Variable neighborhood search
Publisher: Elsevier
Project: National Research University Higher School of Economics, Nizhni Novgorod, Russia, and supported by RSF grant 14-41-00039
Natural Sciences and Engineering Research Council of Canada Discovery Grant (NSERC # 205041?2014)
Mathematical Modelas and Optimization Methods on Large-Scale Systems 
Development of new information and communication technologies, based on advanced mathematical methods, with applications in medicine, telecommunications, power systems, protection of national heritage and education 

Show full item record


checked on May 16, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.