47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) On the Optimality of the Dimensionality Reduction Method Berkeley, California October 21-October 24 ISBN: 0-7695-2720-5
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.56
We investigate the optimality of (1+\in )-approximation algorithms obtained via the dimensionality reduction method. We show that: --Any data structure for the (1+\in )-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use n^{\Omega \left( {1/ \in ^2 } \right)} space. --Any algorithm for the (1+\in )-approximate closest substring problem must run in time exponential in 1/ \in ^{2 - \gamma } for any \gamma > 0 (unless 3SAT can be solved in subexponential time) Both lower bounds are (essentially) tight.
Citation:
Alexandr Andoni, Piotr Indyk, Mihai Patrascu, "On the Optimality of the Dimensionality Reduction Method," focs, pp.449-458, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb