TY - CONF
T1 - Embedding and similarity search for point sets under translation
T2 - Proceedings of the twenty-fourth annual symposium on Computational geometry
Y1 - 2008
A1 - Cho,Minkyoung
A1 - Mount, Dave
KW - EMBEDDING
KW - point pattern matching
KW - randomized algorithms
KW - Similarity Search
AB - Pattern matching in point sets is a well studied problem with numerous applications. We assume that the point sets may contain outliers (missing or spurious points) and are subject to an unknown translation. We define the distance between any two point sets to be the minimum size of their symmetric difference over all translations of one set relative to the other. We consider the problem in the context of similarity search. We assume that a large database of point sets is to be preprocessed so that given any query point set, the closest matches in the database can be computed efficiently. Our approach is based on showing that there is a randomized algorithm that computes a translation-invariant embedding of any point set of size at most n into the L_1 metric, so that with high probability, distances are subject to a distortion that is O(log2 n).
JA - Proceedings of the twenty-fourth annual symposium on Computational geometry
T3 - SCG '08
PB - ACM
CY - New York, NY, USA
SN - 978-1-60558-071-5
UR - http://doi.acm.org/10.1145/1377676.1377731
M3 - 10.1145/1377676.1377731
ER -
TY - JOUR
T1 - A note on the distribution of the number of prime factors of the integers
JF - Information Processing Letters
Y1 - 2008
A1 - Srinivasan, Aravind
KW - Chernoff bounds
KW - Dependent random variables
KW - Primes
KW - Probabilistic number theory
KW - randomized algorithms
KW - Tail bounds
AB - The Chernoff–Hoeffding bounds are fundamental probabilistic tools. An elementary approach is presented to obtain a Chernoff-type upper-tail bound for the number of prime factors of a random integer in { 1 , 2 , … , n } . The method illustrates tail bounds in negatively-correlated settings.
VL - 109
SN - 0020-0190
UR - http://www.sciencedirect.com/science/article/pii/S0020019008002688
CP - 2
M3 - 10.1016/j.ipl.2008.09.010
ER -
TY - JOUR
T1 - A practical approximation algorithm for the LMS line estimator
JF - Computational Statistics & Data Analysis
Y1 - 2007
A1 - Mount, Dave
A1 - Netanyahu,Nathan S.
A1 - Romanik,Kathleen
A1 - Silverman,Ruth
A1 - Wu,Angela Y.
KW - Approximation algorithms
KW - least median-of-squares regression
KW - line arrangements
KW - line fitting
KW - randomized algorithms
KW - robust estimation
AB - The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0 < q ⩽ 1 . This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O ( n 2 ) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε r ⩾ 0 , and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε q ⩾ 0 . We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε q > 0 runs in O ( n log n ) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm's expected running time is O ( n log 2 n ) . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.
VL - 51
SN - 0167-9473
UR - http://www.sciencedirect.com/science/article/pii/S0167947306002921
CP - 5
M3 - 10.1016/j.csda.2006.08.033
ER -
TY - JOUR
T1 - A simple entropy-based algorithm for planar point location
JF - ACM Transactions on Algorithms (TALG)
Y1 - 2007
A1 - Arya,Sunil
A1 - Malamatos,Theocharis
A1 - Mount, Dave
KW - Entropy
KW - expected-case complexity
KW - Point location
KW - polygonal subdivision
KW - randomized algorithms
KW - trapezoidal maps
AB - Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability pz that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.
VL - 3
SN - 1549-6325
UR - http://doi.acm.org/10.1145/1240233.1240240
CP - 2
M3 - 10.1145/1240233.1240240
ER -
TY - JOUR
T1 - Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses
JF - Computational Geometry
Y1 - 2001
A1 - Mount, Dave
A1 - Netanyahu,Nathan S.
KW - Aligned ellipse fitting
KW - Arrangements
KW - Circular arc fitting
KW - computational geometry
KW - randomized algorithms
KW - Range searching
KW - RM estimator
KW - robust estimation
KW - Theil–Sen estimator
AB - Fitting two-dimensional conic sections (e.g., circular and elliptical arcs) to a finite collection of points in the plane is an important problem in statistical estimation and has significant industrial applications. Recently there has been a great deal of interest in robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator. In this paper we introduce nonlinear Theil–Sen and repeated median (RM) variants for estimating the center and radius of a circular arc, and for estimating the center and horizontal and vertical radii of an axis-aligned ellipse. The circular arc estimators have breakdown points of ≈ 21% and 50%, respectively, and the ellipse estimators have breakdown points of ≈ 16% and 50%, respectively. We present randomized algorithms for these estimators, whose expected running times are O(n2logn) for the circular case and O(n3logn) for the elliptical case. All algorithms use O(n) space in the worst case.
VL - 19
SN - 0925-7721
UR - http://www.sciencedirect.com/science/article/pii/S0925772101000098
CP - 1
M3 - 10.1016/S0925-7721(01)00009-8
ER -
TY - CONF
T1 - Finding large independent sets of hypergraphs in parallel
T2 - Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures
Y1 - 2001
A1 - Shachnai,Hadas
A1 - Srinivasan, Aravind
KW - hypergraphs
KW - independent sets
KW - Parallel algorithms
KW - randomized algorithms
AB - A basic problem in hypergraphs is that of finding a large independent set-one of guaranteed size-in a given hypergraph. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza (J. Graph Theory, Vol. 15, pp. 99-107, 1991) have shown a certain lower bound &agr;k(H) on the size of a maximum independent set in a given k-uniform hypergraph H, and have also presented an efficien sequential algorithm to find an independent set of size &agr;k (H). They also show that &agr;k (H) is the size of the maximum independent set for various hypergraph families. Here, we develop the first RNC algorithm to find an independent set of size &agr;k(H), and also derandomize it for various special cases. We also present lower bounds on independent set size and corresponding RNC algorithms for non-uniform hypergraphs.
JA - Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures
T3 - SPAA '01
PB - ACM
CY - New York, NY, USA
SN - 1-58113-409-6
UR - http://doi.acm.org/10.1145/378580.378622
M3 - 10.1145/378580.378622
ER -
TY - JOUR
T1 - Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
JF - Mathematics of Operations ResearchMathematics of Operations Research
Y1 - 2000
A1 - Baveja,Alok
A1 - Srinivasan, Aravind
KW - Approximation algorithms
KW - Disjoint paths
KW - integer programming
KW - Linear programming
KW - multicommodity flow
KW - Packing
KW - randomized algorithms
KW - rounding
KW - Routing
KW - unsplittable flow
AB - Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.
VL - 25
SN - 0364-765X, 1526-5471
UR - http://mor.journal.informs.org/content/25/2/255
CP - 2
M3 - 10.1287/moor.25.2.255.12228
ER -
TY - CONF
T1 - A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria
T2 - Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
Y1 - 1997
A1 - Srinivasan, Aravind
A1 - Teo,Chung-Piaw
KW - Approximation algorithms
KW - covering integer programs
KW - discrete ham-sandwich theorems
KW - Linear programming
KW - packet routing
KW - randomized algorithms
KW - Randomized rounding
KW - rounding theorems
JA - Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
T3 - STOC '97
PB - ACM
CY - New York, NY, USA
SN - 0-89791-888-6
UR - http://doi.acm.org/10.1145/258533.258658
M3 - 10.1145/258533.258658
ER -
TY - CONF
T1 - A practical approximation algorithm for the LMS line estimator
T2 - Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms
Y1 - 1997
A1 - Mount, Dave
A1 - Netanyahu,Nathan S.
A1 - Romanik,Kathleen
A1 - Silverman,Ruth
A1 - Wu,Angela Y.
KW - Approximation algorithms
KW - least median-of-squares regression
KW - line arrangements
KW - line fitting
KW - randomized algorithms
KW - robust estimation
JA - Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms
T3 - SODA '97
PB - Society for Industrial and Applied Mathematics
CY - Philadelphia, PA, USA
SN - 0-89871-390-0
UR - http://dl.acm.org/citation.cfm?id=314161.314349
ER -
TY - CONF
T1 - Randomized and deterministic algorithms for geometric spanners of small diameter
T2 - Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Y1 - 1994
A1 - Arya,S.
A1 - Mount, Dave
A1 - Smid,M.
KW - computational geometry
KW - deletions
KW - deterministic algorithms
KW - directed graph
KW - directed graphs
KW - geometric spanners
KW - insertions
KW - randomised algorithms
KW - randomized algorithms
AB - Let S be a set of n points in IR^{d} and let t gt;1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions
JA - Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
M3 - 10.1109/SFCS.1994.365722
ER -