Probabilistic Analysis of a Relaxation for the k-Median Problem. Revision.
Abstract
This paper provides a probabilistic analysis of the so-called 'strong' linear programming relaxation of the k-median problem. The analysis is performed under four classical models in location theory, the Euclidean, network, tree and uniform cost models. For example, it is shown that, for the Euclidean model and log < or = k < or = n/(log n) squared, the value of the relaxation is almost surely within .3 percent of the optimum k-median value. A similar analysis is perfromed for the other models. It is also shown that, under various assumption, branch and bound algorithms that use this relaxation as a bound must almost surely expand a non-polynomial number of nodes to solve the k-median problem to optimality. Finally, extensive computational experiments are reported. As predicted by the probabilistic analysis, the relaxation was not as tight for the problem instances drawn from the uniform cost model as for the other models.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1986
- Accession Number
- ADA173201
Entities
People
- Alan Frieze
- Colin Cooper
- Gérard Cornuéjols
- Sang Ahn
Organizations
- Carnegie Mellon University