TY - GEN

T1 - Net and prune

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

AU - Har-Peled, Sariel

AU - Raichel, Benjamin

PY - 2013

Y1 - 2013

N2 - We provide a general framework for getting linear time constant factor approximations (and in many cases FPTAS's) to a copious amount of well known and well studied problems in Computational Geometry, such as k-center clustering and furthest nearest neighbor. The new approach is robust to variations in the input problem, and yet it is simple, elegant and practical. In particular, many of these well studied problems which fit easily into our framework, either previously had no linear time approximation algorithm, or required rather involved algorithms and analysis. A short list of the problems we consider include furthest nearest neighbor, k-center clustering, smallest disk enclosing k points, kth largest distance, kth smallest m-nearest neighbor distance, kth heaviest edge in the MST and other spanning forest type problems, problems involving upward closed set systems, and more. Finally, we show how to extend our framework such that the linear running time bound holds with high probability.

AB - We provide a general framework for getting linear time constant factor approximations (and in many cases FPTAS's) to a copious amount of well known and well studied problems in Computational Geometry, such as k-center clustering and furthest nearest neighbor. The new approach is robust to variations in the input problem, and yet it is simple, elegant and practical. In particular, many of these well studied problems which fit easily into our framework, either previously had no linear time approximation algorithm, or required rather involved algorithms and analysis. A short list of the problems we consider include furthest nearest neighbor, k-center clustering, smallest disk enclosing k points, kth largest distance, kth smallest m-nearest neighbor distance, kth heaviest edge in the MST and other spanning forest type problems, problems involving upward closed set systems, and more. Finally, we show how to extend our framework such that the linear running time bound holds with high probability.

KW - Clustering

KW - Linear time

KW - Nets

KW - Optimization

UR - http://www.scopus.com/inward/record.url?scp=84879807607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879807607&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488684

DO - 10.1145/2488608.2488684

M3 - Conference contribution

AN - SCOPUS:84879807607

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 605

EP - 614

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

Y2 - 1 June 2013 through 4 June 2013

ER -