SSSandeep Sen

Sandeep Sen

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Sandeep Sen has a total of 17 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Fully dynamic maximal matching in O(log n) update time

    by Surender Baswana, Manoj Gupta, 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 for a graph with n vertices and m edges is O({(n+ m)}^{0.7072})which is sub-linear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfield designed a randomized data structure that achieves O(log^2 n) 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 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 time per update.

  • The Update Complexity of Selection and Related Problems

    by Manoj Gupta, Yogish Sabharwal, Sandeep Sen


  • Open Access

    Randomised Rounding with Applications

    by Dhiraj Madan, Sandeep Sen

    We develop new techniques for rounding packing integer programs using iterative randomized rounding. It is based on a novel application of multidimensional Brownian motion in $\mathbb{R}^n$. Let $\overset{\sim}{x} \in {[0,1]}^n$ be a fractional feasible solution of a packing constraint $A x \leq 1,\ \ $ $A \in {\{0,1 \}}^{m\times n}$ that maximizes a linear objective function. The independent randomized rounding method of Raghavan-Thompson rounds each variable $x_i$ to 1 with probability $\overset{\sim}{x_i}$ and 0 otherwise. The expected value of the rounded objective function matches the fractional optimum and no constraint is violated by more than $O(\frac{\log m} {\log\log m})$.In contrast, our algorithm iteratively transforms $\overset{\sim}{x}$ to $\hat{x} \in {\{ 0,1\}}^{n}$ using a random walk, such that the expected values of $\hat{x}_i$'s are consistent with the Raghavan-Thompson rounding. In addition, it gives us intermediate values $x'$ which can then be used to bias the rounding towards a superior solution.The reduced dependencies between the constraints of the sparser system can be exploited using {\it Lovasz Local Lemma}. For $m$ randomly chosen packing constraints in $n$ variables, with $k$ variables in each inequality, the constraints are satisfied within $O(\frac{\log (mkp\log m/n) }{\log\log (mkp\log m/n)})$ with high probability where $p$ is the ratio between the maximum and minimum coefficients of the linear objective function. Further, we explore trade-offs between approximation factors and error, and present applications to well-known problems like circuit-switching, maximum independent set of rectangles and hypergraph $b$-matching. Our methods apply to the weighted instances of the problems and are likely to lead to better insights for even dependent rounding.

  • Open Access

    Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

    by Abhash Anand, Surender Baswana, Manoj Gupta, Sandeep Sen

    We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching ${\cal M}$ whose weight is at least $1/8 M^{*}$ where $M^{*}$ is the weight of the maximum weight matching. The algorithm achieves an expected amortized $O(\log n \log \mathcal C)$ time per edge insertion or deletion, where $\mathcal C$ is the ratio of the weights of the highest weight edge to the smallest weight edge in the given graph. Using a simple randomized scaling technique, we are able to obtain a matching whith expected approximation ratio 4.9108.

  • Open Access

    The covert set-cover problem with application to Network Discovery

    by Sandeep Sen, V. N. Muralidhara

    We address a version of the set-cover problem where we do not know the sets initially (and hence referred to as covert) but we can query an element to find out which sets contain this element as well as query a set to know the elements. We want to find a small set-cover using a minimal number of such queries. We present a Monte Carlo randomized algorithm that approximates an optimal set-cover of size $OPT$ within $O(\log N)$ factor with high probability using $O(OPT \cdot \log^2 N)$ queries where $N$ is the input size. We apply this technique to the network discovery problem that involves certifying all the edges and non-edges of an unknown $n$-vertices graph based on layered-graph queries from a minimal number of vertices. By reducing it to the covert set-cover problem we present an $O(\log^2 n)$-competitive Monte Carlo randomized algorithm for the covert version of network discovery problem. The previously best known algorithm has a competitive ratio of $\Omega (\sqrt{n\log n})$ and therefore our result achieves an exponential improvement.

  • A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

    by Surender Baswana, Sandeep Sen

    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 vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t‐spanner of minimum size (number of edges) has been a widely studied and well‐motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t‐spanner of a given weighted graph. Moreover, the size of the t‐spanner computed essentially matches the worst case lower bound implied by a 43‐year old girth lower bound conjecture made independently by Erdős, Bollobás, and Bondy & Simonovits.Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to θ(t)‐levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007