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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2009
34
73
85
http://fcds.cs.put.poznan.pl/fcds2/
Maximum Diversity Problem; Tabu Search; Semidefinite Programming
Roberto Aringhieri; Maurizio Bruglieri; Roberto Cordone
File in questo prodotto:
File
2009-OptimalResultsAndTightBounds4TheMDP.pdf

Accesso aperto

Tipo di file: PDF EDITORIALE
Dimensione 459.35 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2318/61806`