Optimal and Practical Algorithms for Sorting on the PDM 1 (2008)
Sanguthevar Rajasekaran, Sandeep Sen
Abstract. The Parallel Disks Model (PDM) has been proposed to alleviate the I/O bottleneck that arises in the processing of massive data sets. Sorting has been extensively studied on the PDM model...
Cache-Efficient Matrix Transposition (2008)
Siddhartha Chatterjee, Sandeep Sen
We investigate the memory system performance of several algorithms for transposing an N N matrix in-place, where N is large. Specifically, we investigate the relative contributions of the data cache,...
Let G = (V, E) be an undirected weighted graph on |V | = n vertices, and |E | = m edges. A t-spanner of the graph G, for any t ≥ 1, is a subgraph (V, ES), ES ⊆ E, such that the distance between...
Abstract. We describe a deterministic parallel algorithm for linear programming in fixed dimension d that takes poly(log log n) time in the common concurrent read concurrent write (CRCW) PRAM model...
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges. For the problem of transitive closure, the previous best...
Abstract. We present a model that enables us to analyze the running time of an algorithm on a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our...
Chapter 1 CONCENTRATION OF MEASURE FOR RANDOMIZED ALGORITHMS: TECHNIQUES AND ANALYSIS (2007)
Randomized algorithms often turn out to be simpler and faster than their deterministic counterparts. For certain problems, like primality testing, there is no matching polynomial-time deterministic...
Parallel Randomized Algorithms for Selection, Sorting, and Convex Hulls (2007)
Mukund N. Thapa, Designer Morgan Kaufmann, Sanguthevar Rajasekaran, Sandeep Sen
The technique of randomizing an algorithm to improve its eciency
Fast and optimal parallel multidimensional search in PRAMs with applications to (2007)
linear-programming and related problems
An Efficient Output-size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains (2007)
Neelima Gupta, Sandeep Sen, Eep Sen
We describe an efficient parallel algorithm for hidden-surface removal for terrain maps. The algorithm runs in O(log 4 n) steps on the CREW PRAM model with a work bound of O((n + k)polylog(n)) where...
The Hardness of Speeding-up Knapsack (2007)
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS Report Series publications. Copies may be...
Surender Baswana, Ramesh Hariharan, Sandeep Sen
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths in a digraph under deletion of edges. For the problem of transitive closure, the previous best known...
Baswana, Surender, Sen, Sandeep
Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t-spanner of the graph G, for any t 1, is a subgraph (V,ES), ES E, such that the distance between any pair of...
Manan Sanghi, B. Tech, Advisor Prof, Sandeep Sen, Advisor Prof, Rajeev Shorey
Application areas: Bioinformatics, network security, autonomic computing, musical information retrieval, DNA word design, P2P networks and e-commerce Northwestern University (2002-2006) Graduate...
PDM Sorting Algorithms That Take A Small Number Of Passes (2005)
Sanguthevar Rajasekaran, Sandeep Sen
We live in an era of data explosion that necessitates the discovery of novel out-of-core techniques. The I/O bottleneck has to be dealt with in developing out-of-core methods. The Parallel Disk Model...
All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time (2005)
Baswana, Surender, Goyal, Vishrut, Sen, Sandeep, Diekert, Volker, Durand, Bruno
Let $G=(V,E)$ be an unweighted undirected graph on $n$ vertices. Let $\delta(u,v)$ denote the distance between vertices $u,v\inV$. An algorithm is said to compute all-pairs $t$-approximate shortest...
Approximate distance oracle for unweighted graphs in Õ(n²) time (2004)
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly...
Fair adaptive bandwidth allocation: a rate control based active queue management discipline (2004)
Kamra, Abhinav, Saran, Huzur, Sen, Sandeep, Shorey, Rajeev
Active queue management disciplines such as RED and its extensions have been widely studied as mechanisms for providing congestion avoidance, differentiated services and fairness between different...
Baswana, Surender, Hariharan, Ramesh, Sen, Sandeep
This paper presents improved algorithms for the following problem: given an unweighted directed graph G(V,E) and a sequence of on-line shortest-path/reachability queries interspersed with...
Randomized graph data-structures for approximate shortest path problem (2004)
Baswana, Surender, Sen, Sandeep, Sahni, Sartaj, Mehta, Dinesh
Approximate distance oracle for unweighted graphs in Õ(n²) time (2004)
Baswana, Surender, Sen, Sandeep
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly...
Approximate distance oracle for unweighted graphs in Õ(n²) time (2004)
Baswana, Surender, Sen, Sandeep
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly...
Randomized graph data-structures for approximate shortest path problem (2004)
Baswana, Surender, Sen, Sandeep, Sahni, Sartaj, Mehta, Dinesh
Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima (2003)
In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull and the vector maxima problems in three dimensions that are output-size sensitive. Our algorithms...
) edges are required in the worst case for any (2k \Gamma 1)-spanner, which has been proved for k = 1; 2; 3; 5. There exist polynomial time algorithms that can construct spanners with the size that...
Random Sampling Techniques and Parallel Algorithms Design (2003)
Mukund N. Thapa, Sanguthevar Rajasekaran, Sandeep Sen
3.1.1 Randomized Algorithms The technique of randomizing an algorithm to improve its efficiency was first introduced in 1976 independently by Rabin and Solovay & Strassen. Since then, this idea...
Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima (2003)
Neelima Gupta, Sandeep Sen, Eep Sen
In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull and the vector maxima problems in three dimensions that are output-size sensitive. Our algorithms...
A Simple Linear Time Algorithm for Computing Sparse Spanners in Weighted Graphs (2003)
Let G(V; E) be an undirected weighted graph with jV j = n, and jEj = m. A t-spanner of the graph G(V; E) is a sub-graph G(V; ES ), ES E, such that the distance between any pair of vertices in the...
Baswana, Surender, Sen, Sandeep, Hariharan, Ramesh
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...
Baswana, Surender, Sen, Sandeep, Hariharan, Ramesh
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...
Randomized algorithms for geometric optimization problems (2001)
Pankaj K. Agarwal, Sandeep Sen
This chapter reviews randomization algorithms developed in the last few years to solve a wide range of geometric optimization problems. We rst review a number of general techniques, including...
Towards a Theory of Cache-Efficient Algorithms (2000)
Sen, Sandeep, Chatterjee, Siddhartha, Dumir, Neeraj
We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our model, an...
Parallel computational geometry: An approach using randomization (2000)
We describe very general methods for designing efficient parallel algorithms for problems in computational geometry. Although our main focus is the PRAM, we provide strong evidence that these...
Cache-Efficient Matrix Transposition (2000)
Siddhartha Chatterjee, Sandeep Sen
We investigate the memory system performance of several algorithms for transposing an # N matrix in-place, where N is large. Specifically, we investigate the relative contributions of the data cache,...
Cache-Efficient Matrix Transposition (2000)
Siddhartha Chatterjee, Sandeep Sen
We investigate the memory system performance of several algorithms for transposing an N \Theta N matrix in-place, where N is large. Specifically, we investigate the relative contributions of the data...
Randomized Algorithms for Geometric Optimization Problems (2000)
Pankaj K. Agarwal, Sandeep Sen
This chapter reviews randomization algorithms developed in the last few years to solve a wide range of geometric optimization problems. We review a number of general techniques, including randomized...
Towards a Theory of Cache-Efficient Algorithms (Extended Abstract) (2000)
Sandeep Sen, Siddhartha Chatterjee
) Sandeep Sen y Siddhartha Chatterjee z Submitted for publication Abstract We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with...
Parallel Computational Geometry : An approach using randomization (1999)
We describe very general methods for designing efficient parallel algorithms for problems in computational geometry. Although our main focus is the PRAM, we provide strong evidence that these...
Output-Sensitive Algorithms for Uniform Partitions of Points (1999)
Pankaj Agarwal Binay, Pankaj K. Agarwal, Binay K. Bhattacharya, Sandeep Sen, Or R
We consider the following one and two-dimensional bucketing problems: Given a set S of n points in R 1 or R 2 and a positive integer b, distribute the points of S into b equal-size buckets so that...
Towards a Theory of Cache-Efficient Algorithms (1999)
Sandeep Sen, Siddhartha Chatterjee
We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our model, an...
An Improved Output-size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains (1998)
We describe an efficient parallel algorithm for hiddensurface removal for terrain maps. The algorithm runs in O#log 4 n# steps on the CREW PRAM model with a work bound of O##n + k#polylog#n## where n...
Distribution-Sensitive Algorithms (1998)
Sandeep Sen, Eep Sen, Neelima Gupta
We investigate a new paradigm of algorithm design for geometric problems that can be termed distribution-sensitive. Our notion of distribution is more combinatorial in nature than spatial. We...
Optimal, output-sensitive algorithms for constructing planar hulls in parallel (1997)
In this paper we focus on the problem of designing very fast parallel algorithms for the planar convex hull problem that achieve the optimal O(n log H) work-bound for input size n and output size H....
On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm (1997)
Binay K. Bhattacharya, Sandeep Sen
In this paper we present a truly practical and provably optimal O(n log h) time outputsensitive algorithm for the planar convex hull problem. The basic algorithm is similar to the algorithm presented...
Selection in monotone matrices and computing kth nearest neighbors (1996)
Agarwal, Pankaj K., Sen, Sandeep
An m x n matrix A=(ai j),1,i,m and 1,j
Pankaj K. Agarwal, Sandeep Sen
An m � n matrix A �Ž a. i, j, 1�i�m and 1 � j � n, is called a totally monotone matrix if for all i 1, i 2, j 1, j 2, satisfying 1 � i1�i2�m, 1�j1 �j2�n. a �a �a �a. i,...
Optimal Parallel Randomized Algorithms for 3-D Convex Hulls and Related Problems (1992)
We present further applications of random sampling techniques which have been used for deriving ecient parallel algorithms by Reif and Sen [27]. In this paper we present an optimal parallel...
On parallel integer sorting (1992)
Sanguthevar Rajasekaran, Sandeep Sen
Abstract. We present an optimal algorithm for sorting n integers in the range [1,n c] (for any constant c) fortheEREW PRAM model where the word length is n ɛ, for any ɛ>0.Using this algorithm,...
There are now a number of fundamental problems in computational geometry that have optimal algorithms on PRAM models. We present randomized parallel algorithms which execute on an n-processor buttery...
Optimal Randomized Parallel Algorithms For Computational Geometry I (1989)
John H. Reif, Sandeep Sen, Eep Sen
We present parallel algorithms for some fundamental problems in computational geometry which have running time of O(logn) using n processors, with very high probability (approaching 1 as n ! 1)....
An Efficient Output-Sensitive Hidden-Surface Removal Algorithm for Polyhedral Terrains (1988)
In this paper we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly. For example, our results apply...
Two dimensional parallel sorting : a new approach / (1986)
Thesis (M.S.)--University of California, Santa Barbara, 1986.
Chatterjee, Mitali, Jaffe, Charles L., Sundar, Shyam, Basu, Debasis, Sen, Sandeep, Mandal, Chitra
A Leishmania donovani species-specific monoclonal antibody (monoclonal antibody D2) was evaluated for its diagnostic and prognostic potential by a competitive enzyme-linked immunosorbent assay...
Chatterjee, Mitali, Jaffe, Charles L., Sundar, Shyam, Basu, Debasis, Sen, Sandeep, Mandal, Chitra
A Leishmania donovani species-specific monoclonal antibody (monoclonal antibody D2) was evaluated for its diagnostic and prognostic potential by a competitive enzyme-linked immunosorbent assay...
This document in subdirectoryRS/98/14/ The hardness of speeding-up Knapsack
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...