Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Foundations of Computing and Decision Sciences

1 2009

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Maximum Diversity Problem

Sortuj według:

Ogranicz wyniki do:

Optimal results and tight bounds for the maximum diversity problem

Aringhieri R., Bruglieri M., Cordone R.

Foundations of Computing and Decision Sciences

2009

Vol. 34, No. 2

73-85

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.