Steinhaus' Geometric Location Problem for Random Samples in the Plane.
Abstract
The work of H. Steinhaus was apparently the first explicit treatment of the natural question 'How should one choose n points from a mass distributed in the plane so as to best represent the whole? The main objective of this article is to treat a stochastic analogue of Steinhaus' problem. One principle motivation for this stochastic analogue comes from developments in the theory of algorithms. The first of these is the discovery of Karp of an efficient probabilistic algorithm for solving the traveling salesman problem. The second development was the proof of Papadimitriou of the conjecture of Fisher and Hochbaum that the 'Euclidean k-median location problem' is NP-complete.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 11, 1982
- Accession Number
- ADA115376
Entities
People
- Dorit Hochbaum
- J. Michael Steele
Organizations
- Stanford University