The maximum dispersion problem

Elena Fernández, Jörg Kalcsics*, Stefan Nickel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

In the maximum dispersion problem, a given set of objects has to be partitioned into a number of groups. Each object has a non-negative weight and each group has a target weight, which may be different for each group. In addition to meeting the target weight of each group, all objects assigned to the same group should be as dispersed as possible with respect to some distance measure between pairs of objects. Potential applications for this problem come from such diverse fields as the problem of creating study groups or the design of waste collection systems. We develop and compare two different (mixed-) integer linear programming formulations for the problem. We also study a specific relaxation that enables us to derive tight bounds that improve the effectiveness of the formulations. Thereby, we obtain an upper bound by finding in an auxiliary graph subsets of given size with minimal diameter. A lower bound is derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact solution scheme for the maximum dispersion problem and present extensive computational experiments to assess its efficiency.

Original languageEnglish
Pages (from-to)721-730
Number of pages10
JournalOmega
Volume41
Issue number4
Early online date3 Oct 2012
DOIs
Publication statusPublished - Aug 2013

Keywords

  • Chromatic number
  • Combinatorial optimization
  • Dispersion
  • Education
  • Graph theory

Fingerprint

Dive into the research topics of 'The maximum dispersion problem'. Together they form a unique fingerprint.

Cite this