Arrow Research search

Author name cluster

Sudipto Guha

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers
2 author rows

Possible papers

37

ICML Conference 2018 Conference Paper

Semi-Supervised Learning on Data Streams via Temporal Label Propagation

  • Tal Wagner
  • Sudipto Guha
  • Shiva Prasad Kasiviswanathan
  • Nina Mishra

We consider the problem of labeling points on a fast-moving data stream when only a small number of labeled examples are available. In our setting, incoming points must be processed efficiently and the stream is too large to store in its entirety. We present a semi-supervised learning algorithm for this task. The algorithm maintains a small synopsis of the stream which can be quickly updated as new points arrive, and labels every incoming point by provably learning from the full history of the stream. Experiments on real datasets validate that the algorithm can quickly and accurately classify points on a stream with a small quantity of labeled examples.

Details

ICML Conference 2016 Conference Paper

Robust Random Cut Forest Based Anomaly Detection on Streams

  • Sudipto Guha
  • Nina Mishra
  • Gourav Roy
  • Okke Schrijvers

In this paper we focus on the anomaly detection problem for dynamic data streams through the lens of random cut forests. We investigate a robust random cut data structure that can be used as a sketch or synopsis of the input stream. We provide a plausible definition of non-parametric anomalies based on the influence of an unseen point on the remainder of the data, i. e. , the externality imposed by that point. We show how the sketch can be efficiently updated in a dynamic data stream. We demonstrate the viability of the algorithm on publicly available real data.

Details

ICML Conference 2015 Conference Paper

Correlation Clustering in Data Streams

  • Kook Jin Ahn
  • Graham Cormode
  • Sudipto Guha
  • Andrew McGregor 0001
  • Anthony Wirth

In this paper, we address the problem of \emphcorrelation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O(n⋅\textpolylog n)-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the “quality” of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n⋅\textpolylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models.

Details

SODA Conference 2014 Conference Paper

Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite Graphs

  • Kook Jin Ahn
  • Sudipto Guha

We present the first fully polynomial approximation schemes for the maximum weighted (uncapacitated or capacitated) b –Matching problem for nonbipartite graphs that run in time (near) linear in the number of edges, that is, given any δ > 0 the algorithm produces a (1 – δ ) approximation in O ( m poly( δ −1, log n )) time. We provide fractional solutions for the standard linear programming formulations for these problems and subsequently also provide fully polynomial (near) linear time approximation schemes for rounding the fractional solutions. Through these problems as a vehicle, we also present several ideas in the context of solving linear programs approximately using fast primal-dual algorithms. First, we show that approximation algorithms can be used to reduce the width of the formulation, and as a consequence we induce faster convergence. Second, even though the dual of these problems have exponentially many variables and an efficient exact computation of dual weights is infeasible, we can efficiently compute and use a sparse approximation of the dual weights using a combination of (i) adding perturbation to the constraints of the polytope and (ii) amplification followed by thresholding of the dual weights. These algorithms also have the advantage that they use O ( n poly( δ −1, log n )) storage space and only make O ( δ −4 log (1/ δ )log n ) (or better) passes over a read only list of edges. These algorithms therefore can be run in the semi-streaming model and serve as exemplars where algorithms and ideas developed for the streaming model gives us algorithms for combinatorial optimization problems that were not known in absence of the streaming constraints.

Details

I&C Journal 2013 Journal Article

Linear programming in the semi-streaming model with application to the maximum matching problem

  • Kook Jin Ahn
  • Sudipto Guha

In this paper we study linear-programming based approaches to the maximum matching problem in the semi-streaming model. In this model edges are presented sequentially, possibly in an adversarial order, and we are only allowed to use a small space. The allowed space is near linear in the number of vertices (and sublinear in the number of edges) of the input graph. The semi-streaming model is relevant in the context of processing of very large graphs. In recent years, there have been several new and exciting results in the semi-streaming model. However broad techniques such as linear programming have not been adapted to this model. In this paper we present several techniques to adapt and optimize linear-programming based approaches in the semi-streaming model. We use the maximum matching problem as a foil to demonstrate the effectiveness of adapting such tools in this model. As a consequence we improve almost all previous results on the semi-streaming maximum matching problem. We also prove new results on interesting variants.

Details DOI

SODA Conference 2012 Conference Paper

Analyzing graph structure via linear measurements

  • Kook Jin Ahn
  • Sudipto Guha
  • Andrew McGregor 0001

We initiate the study of graph sketching, i. e. , algorithms that use a limited number of linear measurements of a graph to determine the properties of the graph. While a graph on n nodes is essentially O ( n 2 )-dimensional, we show the existence of a distribution over random projections into d -dimensional “sketch” space ( d ≪ n 2 ) such that the relevant properties of the original graph can be inferred from the sketch with high probability. Specifically, we show that: 1. d = O ( n · polylog n ) suffices to evaluate properties including connectivity, k -connectivity, bipartiteness, and to return any constant approximation of the weight of the minimum spanning tree. 2. d = O ( n 1+γ ) suffices to compute graph sparsifiers, the exact MST, and approximate the maximum weighted matchings if we permit O (1/γ)-round adaptive sketches, i. e. , a sequence of projections where each projection may be chosen dependent on the outcome of earlier sketches.

Details

STOC Conference 2007 Conference Paper

Approximation algorithms for budgeted learning problems

  • Sudipto Guha
  • Kamesh Munagala

We present the first approximation algorithms for a large class of budgeted learning problems. One classicexample of the above is the budgeted multi-armed bandit problem. In this problem each arm of the bandithas an unknown reward distribution on which a prior isspecified as input. The knowledge about the underlying distribution can be refined in the exploration phase by playing the arm and observing the rewards. However, there is a budget on the total number of plays allowed during exploration. After this exploration phase,the arm with the highest (posterior) expected reward is hosen for exploitation. The goal is to design the adaptive exploration phase subject to a budget constraint on the number of plays, in order to maximize the expected reward of the arm chosen for exploitation. While this problem is reasonably well understood in the infinite horizon discounted reward setting, the budgeted version of the problem is NP-Hard. For this problem and several generalizations, we provide approximate policies that achieve a reward within constant factor of the reward optimal policy. Our algorithms use a novel linear program rounding technique based on stochastic packing.

Details

FOCS Conference 2007 Conference Paper

Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards

  • Sudipto Guha
  • Kamesh Munagala

We consider a variant of the classic multi-armed bandit problem (MAB), which we call feedback MAB, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process with known parameters. The evolution of the Markov chain happens irrespective of whether the arm is played, and furthermore, the exact state of the Markov chain is only revealed to the player when the arm is played and the reward observed. At most one arm (or in general, M arms) can be played any time step. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is an instance of a partially observable Markov decision process (POMDP), and a special case of the notoriously intractable "restless bandit" problem. Unlike the stochastic MAB problem, the feedback MAB problem does not admit to greedy index-based optimal policies. Vie state of the system at any time step encodes the beliefs about the states of different arms, and the policy decisions change these beliefs - this aspect complicates the design and analysis of simple algorithms. We design a constant factor approximation to the feedback MAB problem by solving and rounding a natural LP relaxation to this problem. As far as we are aware, this is the first approximation algorithm for a POMDP problem.

Details

FOCS Conference 2004 Conference Paper

Machine Minimization for Scheduling Jobs with Interval Constraints

  • Julia Chuzhoy
  • Sudipto Guha
  • Sanjeev Khanna
  • Joseph Naor

The problem of scheduling jobs with interval constraints is a well-studied classical scheduling problem. The input to the problem is a collection of n jobs where each job has a set of intervals on which it can be scheduled. The goal is to minimize the total number of machines needed to schedule all jobs subject to these interval constraints. In the continuous version, the allowed intervals associated with a job form a continuous time segment, described by a release date and a deadline. In the discrete version of the problem, the set of allowed intervals for a job is given explicitly. So far, only an O(log n/( log log n))-approximation is known for either version of the problem, obtained by a randomized rounding of a natural linear programming relaxation of the problem. In fact, we show here that this analysis is tight for both versions of the problem by providing a matching lower bound on the integrality gap of the linear program. Moreover, even when all jobs can be scheduled on a single machine, the discrete case has recently been shown to be /spl Omega/(log log n)-hard to approximate. In this paper, we provide improved approximation factors for the number of machines needed to schedule all jobs in the continuous version of the problem. Our main result is an O(1)-approximation algorithm when the optimal number of machines needed is bounded by a fixed constant. Thus, our results separate the approximability of the continuous and the discrete cases of the problem. For general instances, we strengthen the natural linear programming relaxation in a recursive manner by forbidding certain configurations which cannot arise in an integral feasible solution. This yields an O(OPT)-approximation, where OPT denotes the number of machines needed by an optimal solution. Combined with earlier results, our work implies an O(/spl radic/log n/(log log n))-approximation for any value of OPT.

Details

STOC Conference 2002 Conference Paper

Fast, small-space algorithms for approximate histogram maintenance

  • Anna C. Gilbert
  • Sudipto Guha
  • Piotr Indyk
  • Yannis Kotidis
  • S. Muthukrishnan 0001
  • Martin J. Strauss

(MATH) A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A 3 ." We give a sketching algorithm, that constructs a small sketch from the stream of updates, and a reconstruction algorithm, that produces a B -bucket piecewise-constant representation (histogram) H for A from the sketch, such that || A—H ||≤(1+ε)|| A—H opt ||, where the error || A—H || is either $\ell_1$ (absolute) or $\ell_2$ (root-mean-square) error. The time to process a single update, time to reconstruct the histogram, and size of the sketch are each bounded by poly( B ,log( N ),log|| A ,1/ε. Our result is obtained in two steps. First we obtain what we call a robust histogram approximation for A , a histogram such that adding a small number of buckets does not help improve the representation quality significantly. From the robust histogram, we cull a histogram of desired accruacy and B buckets in the second step. This technique also provides similar results for Haar wavelet representations, under $\ell_2$ error. Our results have applications in summarizing data distributions fast and succinctly even in distributed settings.

Details

STOC Conference 2002 Conference Paper

Near-optimal sparse fourier representations via sampling

  • Anna C. Gilbert
  • Sudipto Guha
  • Piotr Indyk
  • S. Muthukrishnan 0001
  • Martin J. Strauss

(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N , such that $\|\signal-\repn\|_2^2$ is within the factor (1 +ε) of best possible $\|\signal-\repn_\opt\|_2^2$. Our algorithm can access A by reading its values on a sample set T ⊆[0, N ), chosen randomly from a (non-product) distribution of our choice, independent of A . That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log( N )log( M )ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.

Details

STOC Conference 2001 Conference Paper

Data-streams and histograms

  • Sudipto Guha
  • Nick Koudas
  • Kyuseok Shim

Histograms have been used widely to capture data distribution, to represent the data by a small number of step functions. Dynamic programming algorithms which provide optimal construction of these histograms exist, albeit running in quadratic time and linear space. In this paper we provide linear time construction of 1 + ε approximation of optimal histograms, running in polylogarithmic space.

Details

FOCS Conference 2000 Conference Paper

Clustering Data Streams

  • Sudipto Guha
  • Nina Mishra
  • Rajeev Motwani 0001
  • Liadan O'Callaghan

We study clustering under the data stream model of computation where: given a sequence of points, the objective is to maintain a consistently good clustering of the sequence observed so far, using a small amount of memory and time. The data stream model is relevant to new classes of applications involving massive data sets, such as Web click stream analysis and multimedia data analysis. We give constant-factor approximation algorithms for the k-median problem in the data stream model of computation in a single pass. We also show negative results implying that our algorithms cannot be improved in a certain sense.

Details

FOCS Conference 2000 Conference Paper

Hierarchical Placement and Network Design Problems

  • Sudipto Guha
  • Adam Meyerson
  • Kamesh Munagala

Gives constant approximations for a number of layered network design problems. We begin by modeling hierarchical caching, where the caches are placed in layers and each layer satisfies a fixed percentage of the demand (bounded miss rates). We present a constant approximation to the minimum total cost of placing the caches and to the routing demand through the layers. We extend this model to cover more general layered caching scenarios, giving a constant combinatorial approximation to the well-studied multi-level facility location problem. We consider a facility location variant, the load-balanced facility location problem, in which every demand is served by a unique facility and each open facility must serve at least a certain amount of demand. By combining load-balanced facility location with our results on hierarchical caching, we give a constant approximation for the access network design problem.

Details

FOCS Conference 2000 Conference Paper

Nested Graph Dissection and Approximation Algorithms

  • Sudipto Guha

This paper considers approximation algorithms for graph completion problems using the nested dissection paradigm. Given a super-additive function of interest (the smallest planar or chordal extension for example) and a test that relates it to an upper bound of the smallest separator, we provide a framework how to dissect the graph recursively such that no subgraph has more than half the value of its parent, (or is indistinguishable via separator tests) in polynomial time. Interestingly we cannot bound such a function till we have constructed the entire nested dissection. We achieve a partition of the graph with respect to a constant number of such unknown estimator functions simultaneously. Using the framework the paper presents improvements in approximating the chordal completion size (by a factor of log n), operation count (by a factor of log/sup 2/ n and the polynomial term depending on degree) and elimination height. We show that there exists a nested dissection ordering that simultaneously minimizes the elimination height, chordal completion, operation count to within O(log n) factors of the best possible (which may be obtained by three independent orderings) improving the previous existence theorem by factors of log n and d/sup 1/3/ log/sup 3/ n for the latter two. We also show that graphs with small crossing number or fill-in have better approximations of the elimination height, completion and operation count. As a consequence we can approximate the pathwidth, cutwidth, vertex ranking problems better for such graphs. The paper also improves, in some cases, the approximation results of minimum drawing size (number of vertices plus the crossing number) of a planar embedding of a graph, and its layout area on a grid.

Details

FOCS Conference 1999 Conference Paper

Improved Combinatorial Algorithms for the Facility Location and k-Median Problems

  • Moses Charikar
  • Sudipto Guha

We present improved combinatorial approximation algorithms for the uncapacitated facility location and k-median problems. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of 2. 414+/spl epsiv/ in O/spl tilde/(n/sup 2///spl epsiv/) time. This also yields a bicriteria approximation tradeoff of (1+/spl gamma/, 1+2//spl gamma/) for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal dual algorithm for facility location due to K. Jain and V. Vazirani (1999), we get an approximation ratio of 1. 853 in O/spl tilde/(n/sup 3/) time. This is already very close to the approximation guarantee of the best known algorithm which is LP-based. Further combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving 1. 728. We present improved approximation algorithms for capacitated facility location and a variant. We also present a 4-approximation for the k-median problem, using similar ideas, building on the 6-approximation of Jain and Vazirani. The algorithm runs in O/spl tilde/(n/sup 3/) time.

Details

I&C Journal 1999 Journal Article

Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets

  • Sudipto Guha
  • Samir Khuller

In this paper we study the Steiner tree problem in graphs for the case when vertices as well as edges have weights associated with them. A greedy approximation algorithm based on “spider decompositions” was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2ln k, wherekis the number of terminals. However, the best known lower bound on the approximation ratio is (1−o(1))ln k, assuming thatNP⊈DTIME[n O(loglog n)], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of ln k. For the weighted case we develop a new decomposition theorem and generalize the notion of “spiders” to “branch-spiders” that are used to design a new algorithm with a worst case approximation factor of 1. 5ln k. We then generalize the method to yield an approximation factor of (1. 35+ε)ln k, for any constantε>0. These algorithms, although polynomial, are not very practical due to their high running time, since we need to repeatedly find many minimum weight matchings in each iteration. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of 1. 6103ln k. The techniques developed for this algorithm imply a method of approximating node weighted network design problems defined by 0–1 proper functions as well. These new ideas also lead to improved approximation guarantees for the problem of finding a minimum node weighted connected dominating set. The previous best approximation guarantee for this problem was 3ln nby Guha and Khuller. By a direct application of the methods developed in this paper we are able to develop an algorithm with an approximation factor of (1. 35+ε)ln nfor any fixedε>0.

Details DOI

FOCS Conference 1998 Conference Paper

Approximating a Finite Metric by a Small Number of Tree Metrics

  • Moses Charikar
  • Chandra Chekuri
  • Ashish Goel
  • Sudipto Guha
  • Serge A. Plotkin

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.

Details
v2026.09.13