The Maximum Diversity Problem (MDP) consists in selecting a subset M of given cardinality out of a set N, in such a way that the sum of the pairwise diversities between the elements of M is maximum. New instances for this problem have been recently proposed in the literature and new algorithms are currently under study to solve them. As a reference for future research, this paper provides a collection of all best known results for the classical and the new instances, obtained by applying the state-of-the-art algorithms. Most of these results improve the published ones. In addition, the paper provides for the first time a collection of tight upper bounds, proving that some of these instances have been optimally solved. These bounds have been computed by a branch-and-bound algorithm based on a semidefinite formulation of the Quadratic Knapsack Problem (QKP), which is a generalization of the MDP.
Optimal results and tight bounds for the maximum diversity problem / R. Aringhieri, M. Bruglieri, R. Cordone. - In: FOUNDATIONS OF COMPUTING AND DECISION SCIENCE. - ISSN 0867-6356. - 34:2(2009), pp. 73-86.
Optimal results and tight bounds for the maximum diversity problem
R. CordoneUltimo
2009
Abstract
The Maximum Diversity Problem (MDP) consists in selecting a subset M of given cardinality out of a set N, in such a way that the sum of the pairwise diversities between the elements of M is maximum. New instances for this problem have been recently proposed in the literature and new algorithms are currently under study to solve them. As a reference for future research, this paper provides a collection of all best known results for the classical and the new instances, obtained by applying the state-of-the-art algorithms. Most of these results improve the published ones. In addition, the paper provides for the first time a collection of tight upper bounds, proving that some of these instances have been optimally solved. These bounds have been computed by a branch-and-bound algorithm based on a semidefinite formulation of the Quadratic Knapsack Problem (QKP), which is a generalization of the MDP.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.