Accession Number : ADA115376

Title :   Steinhaus' Geometric Location Problem for Random Samples in the Plane.

Descriptive Note : Technical rept.,


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