Conference proceeding
Reductions among high dimensional proximity problems
Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms, pp.769-778
SODA '01
01/09/2001
DOI: 10.1145/301250.301367
Abstract
We present improved running times for a wide range of approximate high dimensional proximity problems. We obtain subquadratic running time for each of these problems. These improved running times are obtained by reduction to Nearest Neighbour queries. The problems we consider in this paper are Approximate Diameter, Approximate Furthest Neighbours, Approximate Discrete Center, Approximate Metric Facility Location, Approximate Bottleneck Matching, and Approximate Minimum Weight Matching.
Details
- Title: Subtitle
- Reductions among high dimensional proximity problems
- Creators
- Ashish GoelPiotr IndykKasturi Varadarajan
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms, pp.769-778
- Series
- SODA '01
- DOI
- 10.1145/301250.301367
- Publisher
- Society for Industrial and Applied Mathematics
- Language
- English
- Date published
- 01/09/2001
- Academic Unit
- Computer Science
- Record Identifier
- 9984259478302771
Metrics
19 Record Views