Optimal Partitioning of a Data Set Based on the p-Median Model

Authors: Brusco, Michael1; Köhn, Hans-Friedrich2

Source: Psychometrika, Volume 73, Number 1, March 2008 , pp. 89-105(17)

Publisher: Springer

Buy & download fulltext article:


Price: $47.00 plus tax (Refund Policy)


Although the K-means algorithm for minimizing the within-cluster sums of squared deviations from cluster centroids is perhaps the most common method for applied cluster analyses, a variety of other criteria are available. The p-median model is an especially well-studied clustering problem that requires the selection of p objects to serve as cluster centers. The objective is to choose the cluster centers such that the sum of the Euclidean distances (or some other dissimilarity measure) of objects assigned to each center is minimized. Using 12 data sets from the literature, we demonstrate that a three-stage procedure consisting of a greedy heuristic, Lagrangian relaxation, and a branch-and-bound algorithm can produce globally optimal solutions for p-median problems of nontrivial size (several hundred objects, five or more variables, and up to 10 clusters). We also report the results of an application of the p-median model to an empirical data set from the telecommunications industry.

Keywords: Lagrangian relaxation; branch and bound; cluster analysis; combinatorial data analysis; heuristics; p-median problem

Document Type: Research Article

DOI: http://dx.doi.org/10.1007/s11336-007-9021-4

Affiliations: 1: Department of Marketing, Florida State University, Tallahassee, FL, 32306-1110, USA, Email: mbrusco@cob.fsu.edu 2: University of Missouri-Columbia, Columbia, USA

Publication date: March 1, 2008

Related content


Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page