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 semide_nite 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
ARINGHIERI, ROBERTO;
2006-01-01
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 semide_nite 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 in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
