The Maximum Diversity Problem consists in extracting a subset of given cardinality from a larger set in such a way that the sum of their pairwise distances is maximum. In this paper we propose a set of bounds for this problem based on semidefinite programming techniques. An extensive computational campaign shows the tightness of the bounds computed with respect to the best known results in literature and to bounds obtained by a linearized integer programming formulation.
Semidefinite bounds for the maximum diversity problem / R. Aringhieri, M. Bruglieri, R. Cordone. - Crema : Università degli Studi di Milano, Polo Didattico e di Ricerca di Crema, 2006 Jul.
Semidefinite bounds for the maximum diversity problem
R. AringhieriPrimo
;R. CordoneUltimo
2006
Abstract
The Maximum Diversity Problem consists in extracting a subset of given cardinality from a larger set in such a way that the sum of their pairwise distances is maximum. In this paper we propose a set of bounds for this problem based on semidefinite programming techniques. An extensive computational campaign shows the tightness of the bounds computed with respect to the best known results in literature and to bounds obtained by a linearized integer programming formulation.File | Dimensione | Formato | |
---|---|---|---|
notaDelPolo95-AringhieriBruglieriCordone.pdf
accesso aperto
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
103.77 kB
Formato
Adobe PDF
|
103.77 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.