TY - GEN
T1 - Proximity algorithms for nearly-doubling spaces
AU - Gottlieb, Lee Ad
AU - Krauthgamer, Robert
N1 - Funding Information:
This work was supported in part by The Israel Science Foundation (grant #452/08), and by a Minerva grant.
PY - 2010
Y1 - 2010
N2 - We introduce a new problem in the study of doubling spaces: Given a point set S and a target dimension d*, remove from S the fewest number of points so that the remaining set has doubling dimension at most d*. We present a bicriteria approximation for this problem, and extend this algorithm to solve a group of proximity problems.
AB - We introduce a new problem in the study of doubling spaces: Given a point set S and a target dimension d*, remove from S the fewest number of points so that the remaining set has doubling dimension at most d*. We present a bicriteria approximation for this problem, and extend this algorithm to solve a group of proximity problems.
UR - http://www.scopus.com/inward/record.url?scp=78149309690&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15369-3_15
DO - 10.1007/978-3-642-15369-3_15
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:78149309690
SN - 3642153682
SN - 9783642153686
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 192
EP - 204
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
Y2 - 1 September 2010 through 3 September 2010
ER -