Skip to Main content Skip to Navigation
Journal articles

Less is more: Solving the Max-Mean diversity problem with variable neighborhood search

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Kathleen TORCK Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 4:35:02 PM
Last modification on : Wednesday, November 3, 2021 - 5:24:24 AM




Jack Brimberg, Nenad Mladenovic, Raca Todosijević, Dragan Urošević. Less is more: Solving the Max-Mean diversity problem with variable neighborhood search. Information Sciences, Elsevier, 2017, 382-383, pp.179-200. ⟨10.1016/j.ins.2016.12.021⟩. ⟨hal-03402528⟩



Record views