|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||Abstract:||
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 Sep 27, 2021
checked on Sep 26, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.