Sudipto Guha

University of Pennsylvania

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Kamesh Munagala

Duke University

Kook Jin Ahn

Creighton University

Andrew McGregor

University of Massachusetts Amherst

Nick Koudas

University of Toronto

Joseph Naor

Technion – Israel Institute of Technology

Samir Khuller

Northwestern University

Baruch Schieber

New Jersey Institute of Technology

Paul J. A. Kenis

University of Illinois Urbana-Champaign

Sarah L. Perry

University of Massachusetts Amherst

Zachary G. Ives

University of Pennsylvania

Cooperative Institutions

Centre National de la Recherche Scientifique

Georgia Institute of Technology

Laboratoire de l'Informatique du Parallélisme

Association pour l'Utilisation du Rein Artificiel

Springer Nature (Germany)

University of Pennsylvania

Stanford University

University of Illinois Urbana-Champaign

Google (United States)

California University of Pennsylvania

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Throughput maximization of real-time scheduling with batching

ACM Transactions on Algorithms (2009)

Amotz Bar-Noy Sudipto Guha Yoav Katz Joseph Naor Baruch Schieber

We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ε) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ε, respectively. We also give approximation algorithms for two special cases when all release times are the same.

Maximization

Batch processing

10.1145/1497290.1497294

Cite

Citations (15)

Greedy strikes back: improved facility location algorithms

Symposium on Discrete Algorithms (1998)

Sudipto Guha Samir Khuller

A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are associated costs for locating the facilities, as well as transportation costs for distributing the commodities. We assume that the transportation costs form a metric. This problem is commonly referred to as theuncapacitated facility locationproblem. Application to bank account location and clustering, as well as many related pieces of work, are discussed by Cornuejols, Nemhauser, and Wolsey. Recently, the first constant factor approximation algorithm for this problem was obtained by Shmoys, Tardos, and Aardal. We show that a simple greedy heuristic combined with the algorithm by Shmoys, Tardos, and Aardal, can be used to obtain an approximation guarantee of 2.408. We discuss a few variants of the problem, demonstrating better approximation factors for restricted versions of the problem. We also show that the problem is max SNP-hard. However, the inapproximability constants derived from the max SNP hardness are very close to one. By relating this problem to Set Cover, we prove a lower bound of 1.463 on the best possible approximation ratio, assumingNP?DTIMEnO(loglogn)].

Set cover problem

Constant (computer programming)

10.5555/314613.315037

Cite

Citations (537)

Asymmetric k -center is log ^* n -hard to approximate

Journal of the ACM (2005)

Julia Chuzhoy Sudipto Guha Eran Halperin Sanjeev Khanna Guy Kortsarz

In the ASYMMETRIC k -CENTER problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point from its center is as small as possible.We show that the ASYMMETRIC k -CENTER problem is hard to approximate up to a factor of log * n − O (1) unless NP ⊆ DTIME ( n log log n ). Since an O (log * n )-approximation algorithm is known for this problem, this resolves the asymptotic approximability of ASYMMETRIC k -CENTER. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric (symmetric) k -Center problem with costs.

Center (category theory)

Triangle inequality

Digraph

10.1145/1082036.1082038

Cite

Citations (54)

Approximation Algorithms for Restless Bandit Problems

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (2009)

Sudipto Guha Kamesh Munagala Peng Shi

In this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any non-trivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. We make progress on this problem by showing that for an interesting and general subclass that we term Monotone bandits, a surprisingly simple and intuitive greedy policy yields a factor 2 approximation. Such greedy policies are termed index policies, and are popular due to their simplicity and their optimality for the stochastic multi-armed bandit problem. The Monotone bandit problem strictly generalizes the stochastic multi-armed bandit problem, and naturally models multi-project scheduling where the state of a project becomes increasingly uncertain when the project is not scheduled. We develop several novel techniques in the design and analysis of the index policy. Our algorithm proceeds by introducing a novel "balance" constraint to the dual of a well-known LP relaxation to the restless bandit problem. This is followed by a structural characterization of the optimal solution by using both the exact primal as well as dual complementary slackness conditions. This yields an interpretation of the dual variables as potential functions from which we derive the index policy and the associated analysis.

10.1137/1.9781611973068.4

Cite

Citations (10)

Streaming and Sublinear Approximation of Entropy and Information Distances

arXiv (Cornell University) (2005)

Sudipto Guha Andrew McGregor Suresh Venkatasubramanian

In many problems in data mining and machine learning, data items that need to be clustered or classified are not points in a high-dimensional space, but are distributions (points on a high dimensional simplex). For distributions, natural measures of distance are not the $\ell_p$ norms and variants, but information-theoretic measures like the Kullback-Leibler distance, the Hellinger distance, and others. Efficient estimation of these distances is a key component in algorithms for manipulating distributions. Thus, sublinear resource constraints, either in time (property testing) or space (streaming) are crucial. We start by resolving two open questions regarding property testing of distributions. Firstly, we show a tight bound for estimating bounded, symmetric f-divergences between distributions in a general property testing (sublinear time) framework (the so-called combined oracle model). This yields optimal algorithms for estimating such well known distances as the Jensen-Shannon divergence and the Hellinger distance. Secondly, we close a $(\log n)/H$ gap between upper and lower bounds for estimating entropy $H$ in this model. In a stream setting (sublinear space), we give the first algorithm for estimating the entropy of a distribution. Our algorithm runs in polylogarithmic space and yields an asymptotic constant factor approximation scheme. We also provide other results along the space/time/approximation tradeoff curve.

Sublinear function

10.48550/arxiv.cs/0508122

Cite

Citations (0)

Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams

Lecture notes in computer science (2009)

Sudipto Guha Zhiyi Huang

10.1007/978-3-642-02927-1_43

Cite

Citations (25)

A Note on Linear Time Algorithms for Maximum Error Histograms

IEEE Transactions on Knowledge and Data Engineering (2007)

Sudipto Guha Kyuseok Shim

Histograms and Wavelet synopses provide useful tools in query optimization and approximate query answering. Traditional histogram construction algorithms, e.g., V-Optimal, use error measures which are the sums of a suitable function, e.g., square, of the error at each point. Although the best-known algorithms for solving these problems run in quadratic time, a sequence of results have given us a linear time approximation scheme for these algorithms. In recent years, there have been many emerging applications where we are interested in measuring the maximum (absolute or relative) error at a point. We show that this problem is fundamentally different from the other traditional {\rm{non}}{\hbox{-}}\ell_\infty error measures and provide an optimal algorithm that runs in linear time for a small number of buckets. We also present results which work for arbitrary weighted maximum error measures.

Sequence (biology)

10.1109/tkde.2007.1039

Cite

Citations (40)

Correlation Clustering in Data Streams

arXiv (Cornell University) (2018)

Kook Jin Ahn Graham Cormode Sudipto Guha Andrew McGregor Anthony Wirth

Clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such as $k$-center, $k$-median, and $k$-means. Such algorithms need to be both time and and space efficient. In this paper, we address the problem of correlation 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\cdot \ \mbox{polylog}~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. Unfortunately, the standard LP and SDP formulations are not obviously solvable in $O(n\cdot \mbox{polylog}~n)$-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling.

Streaming algorithm

10.48550/arxiv.1812.02023

Cite

Citations (0)

Behavioral Intervention and Non-Uniform Bootstrap Percolation

arXiv (Cornell University) (2015)

Peter H. Ballen Sudipto Guha

Bootstrap percolation is an often used model to study the spread of diseases, rumors, and information on sparse random graphs. The percolation process demonstrates a critical value such that the graph is either almost completely affected or almost completely unaffected based on the initial seed being larger or smaller than the critical value. To analyze intervention strategies we provide the first analytic determination of the critical value for basic bootstrap percolation in random graphs when the vertex thresholds are nonuniform and provide an efficient algorithm. This result also helps solve the problem of "Percolation with Coinflips" when the infection process is not deterministic, which has been a criticism about the model. We also extend the results to clustered random graphs thereby extending the classes of graphs considered. In these graphs the vertices are grouped in a small number of clusters, the clusters model a fixed communication network and the edge probability is dependent if the vertices are in close or far clusters. We present simulations for both basic percolation and interventions that support our theoretical results.

Percolation (cognitive psychology)

Continuum percolation theory

Percolation Theory

10.48550/arxiv.1512.00834

Cite

Citations (1)

A Constant Factor Approximation for the Single Sink Edge Installation Problem

SIAM Journal on Computing (2009)

Sudipto Guha Adam Meyerson Kamesh Munagala

We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of $O(\log|R|)$, where R is the set of sources. We also present a better constant approximation to the related Access Network Design problem. Our algorithms are randomized and combinatorial. As a subroutine in our algorithm, we use an interesting variant of facility location with lower bounds on the amount of demand an open facility needs to serve. We call this variant load balanced facility location and present a constant factor approximation for it, while relaxing the lower bounds by a constant factor.

Constant (computer programming)

Subroutine

Randomized Algorithm

10.1137/050643635

Cite

Citations (34)