Accession Number : ADA115376
Title : Steinhaus' Geometric Location Problem for Random Samples in the Plane.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CA DEPT OF STATISTICS
Personal Author(s) : Hochbaum,Dorit ; Steele,J Michael
PDF Url : ADA115376
Report Date : 11 May 1982
Pagination or Media Count : 25
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.
Descriptors : *Probability, Algorithms, Stochastic control, Problem solving, Random variables, Sampling, Geometry
Subject Categories : Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE