BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Sandeep Sen

Sandeep Sen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational GeometryDistributed, Parallel, and Cluster Computingmath.OC

Catalog footprint

What is connected

10works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2016arXiv

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

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Improvable Knapsack Problems

We consider a variant of the knapsack problem, where items are available with different possible weights. Using a separate budget for these item improvements, the question is: Which items should be improved to which degree such that the resulting classic knapsack problem yields maximum profit? We present a detailed analysis for several cases of improvable knapsack problems, presenting constant factor approximation algorithms and two PTAS.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Randomised Rounding with Applications

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximation Algorithms for Budget Constrained Network Upgradeable Problems

We study budget constrained network upgradeable problems. We are given an undirected edge weighted graph $G=(V,E)$ where the weight an edge $e \in E$ can be upgraded for a cost $c(e)$. Given a budget $B$ for improvement, the goal is to find a subset of edges to be upgraded so that the resulting network is optimum for $B$. The results obtained in this paper include the following. Maximum Weight Constrained Spanning Tree We present a randomized algorithm for the problem of weight upgradeable budget constrained maximum spanning tree on a general graph. This returns a spanning tree $\mathcal{T}^{'}$ which is feasible within the budget $B$, such that $\Pr [ l(\mathcal{T}^{'}) \geq (1-ε)\text{OPT}\text{ , } c(\mathcal{T}^{'} ) \leq B] \ge 1-\frac{1}{n}$ (where $l$ and $c$ denote the length and cost of the tree respectively), for any fixed $ε>0$, in time polynomial in $|V|=n$, $|E|=m$. Our results extend to the minimization version also. Previously Krumke et. al. \cite{krumke} presented a$(1+\frac{1}γ, 1+ γ)$ bicriteria approximation algorithm for any fixed $γ>0$ for this problem in general graphs for a more general cost upgrade function. The result in this paper improves their 0/1 cost upgrade model. Longest Path in a DAG We consider the problem of weight improvable longest path in a $n$ vertex DAG and give a $O(n^3)$ algorithm for the problem when there is a bound on the number of improvements allowed. We also give a $(1-ε)$-approximation which runs in $O(\frac{n^4}ε)$ time for the budget constrained version. Similar results can be achieved also for the problem of shortest paths in a DAG.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improved Randomized Rounding using Random Walks

We describe a novel algorithm for rounding packing integer programs based on multidimensional Brownian motion in $\mathbb{R}^n$. Starting from an optimal fractional feasible solution $\bar{x}$, the procedure converges in polynomial time to a distribution over (possibly infeasible) point set $P \subset {\{0,1 \}}^n$ such that the expected value of any linear objective function over $P$ equals the value at $\bar{x}$. This is an alternate approach to the classical randomized rounding method of Raghavan and Thompson \cite{RT:87}. Our procedure is very general and in conjunction with discrepancy based arguments, yield efficient alternate methods for rounding other optimization problems that can be expressed as packing ILPs including disjoint path problems and MISR.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A simple D^2-sampling based PTAS for k-means and other Clustering Problems

Given a set of points $P \subset \mathbb{R}^d$, the $k$-means clustering problem is to find a set of $k$ {\em centers} $C = \{c_1,...,c_k\}, c_i \in \mathbb{R}^d,$ such that the objective function $\sum_{x \in P} d(x,C)^2$, where $d(x,C)$ denotes the distance between $x$ and the closest center in $C$, is minimized. This is one of the most prominent objective functions that have been studied with respect to clustering. $D^2$-sampling \cite{ArthurV07} is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points $P \subseteq \mathbb{R}^d$, the first point is chosen uniformly at random from $P$. Subsequently, a point from $P$ is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled points. $D^2$-sampling has been shown to have nice properties with respect to the $k$-means clustering problem. Arthur and Vassilvitskii \cite{ArthurV07} show that $k$ points chosen as centers from $P$ using $D^2$-sampling gives an $O(\log{k})$ approximation in expectation. Ailon et. al. \cite{AJMonteleoni09} and Aggarwal et. al. \cite{AggarwalDK09} extended results of \cite{ArthurV07} to show that $O(k)$ points chosen as centers using $D^2$-sampling give $O(1)$ approximation to the $k$-means objective function with high probability. In this paper, we further demonstrate the power of $D^2$-sampling by giving a simple randomized $(1 + ε)$-approximation algorithm that uses the $D^2$-sampling in its core.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model

In this paper we present randomized algorithms for sorting and convex hull that achieves optimal performance (for speed-up and cache misses) on the multicore model with private cache model. Our algorithms are cache oblivious and generalize the randomized divide and conquer strategy given by Reischuk and Reif and Sen. Although the approach yielded optimal speed-up in the PRAM model, we require additional techniques to optimize cache-misses in an oblivious setting. Under a mild assumption on input and number of processors our algorithm will have optimal time and cache misses with high probability. Although similar results have been obtained recently for sorting, we feel that our approach is simpler and general and we apply it to obtain an optimal parallel algorithm for 3D convex hulls with similar bounds. We also present a simple randomized processor allocation technique without the explicit knowledge of the number of processors that is likely to find additional applications in resource oblivious environments.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The covert set-cover problem with application to Network Discovery

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 $Ω(\sqrt{n\log n})$ and therefore our result achieves an exponential improvement.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The update complexity of selection and related problems

We present a framework for computing with input data specified by intervals, representing uncertainty in the values of the input parameters. To compute a solution, the algorithm can query the input parameters that yield more refined estimates in form of sub-intervals and the objective is to minimize the number of queries. The previous approaches address the scenario where every query returns an exact value. Our framework is more general as it can deal with a wider variety of inputs and query responses and we establish interesting relationships between them that have not been investigated previously. Although some of the approaches of the previous restricted models can be adapted to the more general model, we require more sophisticated techniques for the analysis and we also obtain improved algorithms for the previous model. We address selection problems in the generalized model and show that there exist 2-update competitive algorithms that do not depend on the lengths or distribution of the sub-intervals and hold against the worst case adversary. We also obtain similar bounds on the competitive ratio for the MST problem in graphs.

0 citations0 reviewsNo code linkedOpen access