Sandeep Sen

TCS Journal 2012 Journal Article

Preface

• Subhas C. Nandy
• Sandeep Sen

FOCS Conference 2011 Conference Paper

Fully Dynamic Maximal Matching in O (log n) Update Time

• Surender Baswana
• Manoj Gupta 0002
• Sandeep Sen

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes $O( \log n)$ expected amortized time for each edge update where $n$ is the number of vertices in the graph. While there is a trivial $O(n)$ algorithm for edge update, the previous best known result for this problem was due to Ivkovi\'c and Llyod\cite{llyod}. For a graph with $n$ vertices and $m$ edges, they give an $O( {(n+ m)}^{0. 7072})$ update time algorithm which is sub linear only for a sparse graph. %To the best of our knowledge this %is the first polylog update time for maximal matching that implies an % exponential improvement from the previous results. For the related problem of maximum matching, Onak and Rubinfeld \cite{onak} designed a randomized data structure that achieves $O(\log^2 n)$ expected amortized time for each update for maintaining a $c$-approximate maximum matching for some large constant $c$. In contrast, we can maintain a factor two approximate maximum matching in $O(\log n )$ expected amortized time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes $O(\log n )$expected amortized time per update.

TCS Journal 2009 Journal Article

All-pairs nearly 2-approximate shortest paths in O ( n 2 polylog n ) time

• Surender Baswana
• Vishrut Goyal
• Sandeep Sen

Let G = ( V, E ) be an unweighted undirected graph on | V | = n vertices and | E | = m edges. Let δ ( u, v ) denote the distance between vertices u, v ∈ V. An algorithm is said to compute all-pairs t -approximate shortest-paths/distances, for some t ≥ 1, if for each pair of vertices u, v ∈ V, the path/distance reported by the algorithm is not longer/greater than t ⋅ δ ( u, v ). This paper presents two extremely simple randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm requires an expected O ( m 2 / 3 n log n + n 2 ) time, and for any u, v ∈ V reports a distance no greater than 2 δ ( u, v ) + 1. Our second algorithm requires an expected O ( n 2 log 3 / 2 n ) time, and for any u, v ∈ V reports a distance bounded by 2 δ ( u, v ) + 3.

FOCS Conference 2004 Conference Paper

A Simple Linear Time (1+έ)-Approximation Algorithm for k-Means Clustering in Any Dimensions

• Amit Kumar 0001
• Yogish Sabharwal
• Sandeep Sen

We present the first linear time (1 + /spl epsiv/)-approximation algorithm for the k-means problem for fixed k and /spl epsiv/. Our algorithm runs in O(nd) time, which is linear in the size of the input. Another feature of our algorithm is its simplicity - the only technique involved is random sampling.

SODA Conference 2004 Conference Paper

Approximate distance oracles for unweighted graphs in Õ(n 2 ) time

• Surender Baswana
• Sandeep Sen

SODA Conference 2003 Conference Paper

Maintaining all-pairs approximate shortest paths under deletion of edges

• Surender Baswana
• Ramesh Hariharan
• Sandeep Sen

STOC Conference 2002 Conference Paper

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

• Surender Baswana
• Ramesh Hariharan
• Sandeep Sen

We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O (1) query time, require O (\min(m, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O (n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O (n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O (n^{\frac{4}{3}}\sqrt[3]{\log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O (\frac{n^3}{m} \log^2 n)$ amortized update time and answers a distance query in O (1) time. This improves the previous best known update bound by a factor of log n . For maintaining all-pairs shortest paths, we present an algorithm that achieves O (\min(n^{\frac{3}{2}} \sqrt{\log n}, \frac{n^3}{m} \log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O (\sqrt{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+ε) approximate shortest paths/distances, for any ε > 0 , that achieves a sub-quadratic update time of O ( n log 2 n + \frac{n^2}{\sqrt{\epsilon m}}\sqrt{\log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O (1/ n c ) for any constant c ).

SODA Conference 2000 Conference Paper

Towards a theory of cache-efficient algorithms

• Sandeep Sen
• Siddhartha Chatterjee

TCS Journal 1997 Journal Article

Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems

• Sandeep Sen

We present lower bounds on the number of rounds required to solve a decision problem in the parallel algebraic decision tree model. More specifically, we show that any parallel algorithm in the fixed degree algebraic decision tree model that answers membership queries in W ⊆R n using p processors, requires Ω ( sol|log |W| nlog ( p n )) rounds where |W| is the number of c components of W. This implies non-trivial lower bounds for parallel algorithms that use a superlinear number of processors, namely, that the speed-up obtainable in such cases is not proportional to the number of processors. We further prove a similar result for the average case complexity. We give applications of this result to various fundamental problems in computational geometry like convex-hull construction and trapezoidal decomposition and also present algorithms with matching upper bounds. The algorithms extend Reif and Sen's work in parallel computational geometry to the sublogarithmic time range based on recent progress in padded-sorting. A corollary of our result strengthens the known lower-bound of parallel sorting from the parallel comparison tree model to the more powerful bounded-degree decision tree.

STOC Conference 1989 Conference Paper

Polling: A New Randomized Sampling Technique for Computational Geometry

• John H. Reif
• Sandeep Sen

We introduce a new randomized sampling technique, called Polling which has applications to deriving efficient parallel algorithms. As an example of its use in computational geometry, we present an optimal parallel randomized algorithm for intersection of half-spaces in three dimensions. Because of well-known reductions, our methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, Voronoi diagram of point sites on a plane and Euclidean minimal spanning tree. Our algorithms run in time T = O(logn) for worst-case inputs and uses P = O(n) processors in a CREW PRAM model where n is the input size. They are randomized in the sense that they use a total of only O(log 2 n ) random bits and terminate in the claimed time bound with probability 1 - n -α for any α > 0. They are also optimal in P . T product since the sequential time bound for all these problems is Ω( nlogn ). The best known determistic parallel algorithms for 2-D Voronoi-diagram and 3-D Convex hull run in O(log 2 n ) and O(log 2 nlog * n ) time respectively while using O(n) processors.

FOCS Conference 1986 Conference Paper

The Distance Bound for Sorting on Mesh-Connected Processor Arrays Is Tight (Preliminary Report)

• Yiming Ma
• Sandeep Sen
• Isaac D. Scherson

In this paper, We consider the problem of sorting n2 numbers, initially distributed randomly in an n × n mesh-connected processor array with one element per processor. We show a lower bound, based on distance arguments, of 4n routing steps on mesh-connected processors operating in an SIMD mode with no wraparounds in rows or columns, We present an algorithm using a novel approach, which is optimal upto the conslant of the leading term, and hence, succeed in proving the tightness of the lower bound based on distance. Keeping in mind the practical difficulties in implementation of this algorithm, we also present an extremely practical O(n) algorithm amenable for VLSI implementation and for existing mesh- connected computers. All the results in this paper were derived by using a new method of analysis inspired by the discovery of shear-sort or row-column sort.