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. Aringhieri
Primo
;
R. Cordone
Ultimo
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.
lug-2006
Settore INF/01 - Informatica
Working Paper
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.
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/25782
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact