Boosted Sampling: Approximation Algorithms forStochastic Optimization (2009)
ABSTRACT Several combinatorial optimization problems choose elements tominimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem,...
How to Complete a Doubling Metric (2009)
In recent years, considerable advances have been made in the study of properties of metric spaces in terms of their doubling dimension. This line of research has not only enhanced our understanding...
Secretary Problems: Weights and Discounts (2009)
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar
The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an...
Infrastructure Leasing Problems ⋆ (2009)
Barbara M. Anthony, Anupam Gupta
Abstract. Consider the following Steiner Tree leasing problem. Given a graph G = (V, E) with root r, and a sequence of terminal sets Dt ⊆ V for each day t ∈ [T]. A feasible solution to the...
Where’s the Winner? Max-Finding and Sorting with Metric Costs (2009)
Abstract. Traditionally, a fundamental assumption in evaluating the performance of algorithms for sorting and selection has been that comparing any two elements costs one unit (of time, work, etc.);...
Anupam Gupta, Robert Krauthgamer, James R. Lee
fractals, and low-distortion embeddings
Stochastic Steiner Tree with Non-Uniform Inflation (2009)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Amit Kumar, Sloan Fellowship
Abstract. We study the Steiner Tree problem in the model of two-stage stochastic optimization with non-uniform inflation factors, and give a poly-logarithmic approximation factor for this problem. In...
Approximating TSP on Metrics with Bounded Global Growth ∗ (2009)
The Traveling Salesman Problem (TSP) is a canonical NP-complete problem which is known to be MAX-SNP hard even on Euclidean metrics (of high dimensions) [40]. In order to circumvent this hardness,...
Steiner points in tree metrics don’t (really) help (2009)
Consider an edge-weighted tree T = (V, E, w: E → R +), in which a subset R of the nodes (called the required nodes) are colored red and the remaining nodes in S = V \R are colored black (and called...
Secretary Problems: Weights and Discounts (2009)
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar
The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an...
An O(log 2 k)-competitive Algorithm for Metric Bipartite Matching (2009)
Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph (seffi Naor
Abstract. We consider the online metric matching problem. In this problem, we are given a graph with edge weights satisfying the triangle inequality, and k vertices that are designated as the right...
Stochastic Analyses for Online Combinatorial Optimization Problems (2009)
Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski
In this paper, we study online algorithms when the input is not chosen adversarially, but consists of draws from some given probability distribution. While this model has been studied for online...
Anupam Gupta, R. Ravi, Amitabh Sinha
Real-world networks often need to be designed under uncertainty, with only partial information and predictions of demand available at the outset of the design process. The field of stochastic...
Stochastic Steiner trees without a root (2009)
Abstract. This paper considers the Steiner tree problem in the model of twostage stochastic optimization with recourse. This model, the focus of much recent research [1–4], tries to capture the...
É.: Cost-sharing mechanisms for network design (2009)
Anupam Gupta, Aravind Srinivasan, Éva Tardos
We consider a single-source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pages 365–372, 2003) developed a simple method for a...
Approximate Clustering without the Approximation (2009)
Maria-florina Balcan, Avrim Blum, Anupam Gupta
Approximation algorithms for clustering points in metric spaces is a flourishing area of research, with much research effort spent on getting a better understanding of the approximation guarantees...
Scheduling with Outliers (2009)
Gupta, Anupam, Krishnaswamy, Ravishankar, Kumar, Amit, Segev, Danny
In classical scheduling problems, we are given jobs and machines, and have to schedule all the jobs to minimize some objective function. What if each job has a specified profit, and we are no longer...
Differentially Private Approximation Algorithms (2009)
Gupta, Anupam, Ligett, Katrina, McSherry, Frank, Roth, Aaron, Talwar, Kunal
Consider the following problem: given a metric space, some of whose points are "clients", open a set of at most $k$ facilities to minimize the average distance from the clients to these facilities....
On Configuring BGP Route Reflectors (2009)
Yuri Breitbart, Minos Garofalakis, Anupam Gupta, Amit Kumar, Rajeev Rastogi
Abstract — The Border Gateway Protocol (BGP) is the standard protocol for exchanging routing information between border routers of Autonomous Systems (ASes) in today’s Internet. Within an AS,...
Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V,d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2squared” metrics. We show how to...
Anupam Gupta, Robert Krauthgamer, James R. Lee
fractals, and low-distortion embeddings
Cost-Sharing Mechanisms for Network Design \Lambda (2008)
single-source rent-or-buy problem that also yields the best-known approximation ratio for the problem. Weshow how to use a variant of this method to develop an approximately budget-balanced and group...
Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V, d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2-squared” metrics. We show how to...
Anupam Gupta, Aravind Srinivasan, 'eva Tardos
Abstract. We consider a single source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pages 365-372, 2003) developed a simple...
Boosted Sampling: Approximation Algorithms forStochastic Optimization (2008)
ABSTRACT Several combinatorial optimization problems choose elements tominimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem,...
Abstract Stochastic Analyses for Online Combinatorial Optimization Problems (2008)
Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski
In this paper, we study online algorithms when the input is not chosen adversarially, but consists of draws from some given probability distribution. While this model has been studied for online...
Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V, d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2squared” metrics. We show how to...
Approximation algorithms for minimizing (2008)
Kedar Dhamdhere, Anupam Gupta, R. Ravi
average distortion
Cost-Sharing Mechanisms for Network Design \Lambda (2008)
Abstract We consider a single source network design problem from a game-theoretic perspective. Gupta, Kumarand Roughgarden [4] developed a simple method for single source rent-or-buy problem that...
Simpler Analyses of Local Search Algorithms for Facility Location (2008)
Gupta, Anupam, Tangwongsan, Kanat
We study local search algorithms for metric instances of facility location problems: the uncapacitated facility location problem (UFL), as well as uncapacitated versions of the $k$-median, $k$-center...
Cost-Sharing Mechanisms for Network Design \Lambda (2008)
single-source rent-or-buy problem that also yields the best-known approximation ratio for the problem. Weshow how to use a variant of this method to develop an approximately budget-balanced and group...
Stochastic Combinatorial Optimization I: Two Stage Optimization with Recourse (2008)
The field of stochastic optimization goes back at least 50 years, with the classical work of Dantzig and Beale, and a rich flourishing body of work. The study of this area through the viewglass of...
LP Rounding Approximation Algorithms for Stochastic Network Design (2008)
Anupam Gupta, R. Ravi, Amitabh Sinha
We study the Steiner tree problem and the single-cable single-sink network design problem under a two-stage stochastic model with recourse and finitely many scenarios. In these models, some edges are...
Prof Eva Tardos, Vlady Ravelomanana, Herve Daudé, Ivan Rapaport, Karol Suchan, Ioan Todinca, ...
15:00-15:20 Computing the growth of the number of overlap-free words with spectra
Stochastic Combinatorial Optimization II: Extensions and Online Problems (2008)
The field of stochastic optimization goes back at least 50 years, with the classical work of Dantzig and Beale, and a rich flourishing body of work. The study of this area through the viewglass of...
Anupam Gupta, Martin P Ál, Google Inc, Tim Roughgarden
We present constant-factor approximation algorithms for several widely-studied NP-hard optimization problems in network design, including the multicommodity rent-or-buy, virtual private network...
Pricing Tree Access Networks with Connected Backbones (2008)
Vineet Goyal, Anupam Gupta, Stefano Leonardi, R. Ravi
Consider the following network subscription pricing problem. We are given a graph G = (V, E) with a root r, and potential customers are companies headquartered at r with locations at a subset of...
LP Rounding Approximation Algorithms for Stochastic Network Design (2008)
Anupam Gupta, R. Ravi, Amitabh Sinha
We study the Steiner tree problem and the single-cable single-sink network design problem under a two-stage stochastic model with recourse and finitely many scenarios. In these models, some edges are...
ABSTRACT Boosted Sampling: Approximation Algorithms for Stochastic Optimization (2008)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem, for...
Stochastic Steiner Tree with Non-Uniform Inflation (2008)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Amit Kumar
Abstract. We study the Steiner Tree problem in the model of two-stage stochastic optimization with non-uniform inflation factors, and give a poly-logarithmic approximation factor for this problem. In...
An investigation of mechanical properties of Joshi External Stabilising System (JESS) (2008)
Mishra, Sanjay K., Gupta, Anupam, Kumar, Rajeev, Sharma, V. P.
Joshi External Stabilising System (JESS ) has been used for more than 20 years in clinics for treatment of variety of musculoskeletal disorders. However, despite its popular use in India, to the best...
An investigation of mechanical properties of Joshi External Stabilising System (JESS) (2008)
Mishra, Sanjay K., Gupta, Anupam, Kumar, Rajeev, Sharma, V. P.
Joshi External Stabilising System (JESS ) has been used for more than 20 years in clinics for treatment of variety of musculoskeletal disorders. However, despite its popular use in India, to the best...
An investigation of mechanical properties of Joshi External Stabilising System (JESS) (2008)
Mishra, Sanjay K., Gupta, Anupam, Kumar, Rajeev, Sharma, V. P.
Joshi External Stabilising System (JESS ) has been used for more than 20 years in clinics for treatment of variety of musculoskeletal disorders. However, despite its popular use in India, to the best...
Robust submodular observation selection (2008)
Andreas Krause, Carlos Guestrin, H. Brendan Mcmahan, Google Inc, Anupam Gupta
In many applications, one has to actively select among a set of expensive observations before making an informed decision. For example, in environmental monitoring, we want to select locations to...
Lecture 9: Hardness of Max-Ek-Indep.-Set and A.-k-Center (2008)
Lecturer Ryan O’donnell, Anupam Gupta, Scribe Eric Blais
In this lecture, we complete the proof of hardness of approximation for the Max-Ek-Hypergraph-Indepedent-Set problem. We also give a proof of hardness of approximation for the Asymmetric k-Center...
A plant location guide for the unsure (2008)
Barbara M. Anthony, Vineet Goyal, Anupam Gupta, Viswanath Nagarajan
This paper studies an extension of the k-median problem where we are given a metric space (V, d) and not just one but m client sets {Si ⊆ V} m i=1, and the goal is to open k facilities F to...
Robust submodular observation selection (2008)
Andreas Krause, H. Brendan Mcmahan, Carlos Guestrin, Anupam Gupta, Chris Williams, C○ Andreas Krause, ...
In many applications, one has to actively select among a set of expensive observations before making an informed decision. For example, in environmental monitoring, we want to select locations to...
Efficient Algorithms for Path Problems in Weighted Graphs (2008)
Virginia Vassilevska, Manuel Blum, Anupam Gupta
The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring...
All-Norms and All-L_p-Norms Approximation Algorithms (2008)
Golovin, Daniel, Gupta, Anupam, Kumar, Amit, Tangwongsan, Kanat
In many optimization problems, a solution can be viewed as ascribing a ``cost'' to each client, and the goal is to optimize some aggregation of the per-client costs. We often optimize some $L_p$-norm...
An investigation of mechanical properties of Joshi External Stabilising System (JESS) (2008)
Mishra, Sanjay K., Gupta, Anupam, Kumar, Rajeev, Sharma, V. P.
Joshi External Stabilising System (JESS ) has been used for more than 20 years in clinics for treatment of variety of musculoskeletal disorders. However, despite its popular use in India, to the best...
An investigation of mechanical properties of Joshi External Stabilising System (JESS) (2008)
Mishra, Sanjay K., Gupta, Anupam, Kumar, Rajeev, Sharma, V. P.
Joshi External Stabilising System (JESS ) has been used for more than 20 years in clinics for treatment of variety of musculoskeletal disorders. However, despite its popular use in India, to the best...
How to Complete a Doubling Metric (2007)
In recent years, considerable advances have been made in the study of properties of metric spaces in terms of their doubling dimension. This line of research has not only enhanced our understanding...
Cuts, Trees and l 1 -Embeddings of Graphs (2007)
Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
Motivated by many recent algorithmic applications, this paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred when the graph...
Definition Metric Space, Lecturer Yair, Bartal Scribe, Anupam Gupta
pace M with a distance function d (which is symmetric in most of the cases we consider). There are k servers in this space. The request sequence is oe = oe 1 oe 2 : : :, where oe i is a point in M ....
MultiProtocol Label Switching (MPLS) [6, 11] is newly proposed routing protocol for the Internet, and is becoming widely popular. In this paper, we initiate a theoretical study of the protocol, and...
The study of the effect of priced information on basic algorithmic problems was initiated by the paper of Charikar et al. [5]. In this paper, we continue the study of sorting and selection in the...
Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also...
Anupam Gupta, Martin Pal, Tim Roughgarden
We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of...
Dial a Ride from k-forest (2007)
Gupta, Anupam, Hajiaghayi, MohammadTaghi, Nagarajan, Viswanath, Ravi, R.
The k-forest problem is a common generalization of both the k-MST and the dense-$k$-subgraph problems. Formally, given a metric space on $n$ vertices $V$, with $m$ demand pairs $\subseteq V \times V$...
The Embedding Distortion Bounds from Coloring Finding the Coloring (2007)
Low-distortion Embeddings, Anupam Gupta, Robert Krauthgamer, James R. Lee
◮ Given a tree metric, we’ll use path partitions to embed the vertices into ℓp for 1 ≤ p ≤ ∞. ◮ We’ll bound the distortion of the embedding in terms of the doubling constant...
Dial a ride from k-Forest (2007)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi
The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a “target ”...
Selecting observations against adversarial objectives (2007)
Andreas Krause, H. Brendan Mcmahan, Google Inc, Carlos Guestrin, Anupam Gupta
In many applications, one has to actively select among a set of expensive observations before making an informed decision. Often, we want to select observations which perform well when evaluated with...
All-norms and all-Lp-norms approximation algorithms (2007)
Daniel Golovin, Anupam Gupta, Amit Kumar, Kanat Tangwongsan
work was done while the author was at Max-Planck-Institut für Informatik, Saarbrücken, Germany.
Selecting observations against adversarial objectives (2007)
Andreas Krause, Carlos Guestrin, H. Brendan Mcmahan, Google Inc, Anupam Gupta
In many applications, one has to actively select among a set of expensive observations before making an informed decision. Often, we want to select observations which perform well when evaluated with...
Dial a ride from k-Forest (2007)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi
The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a “target ”...
Selecting observations against adversarial objectives (2007)
Andreas Krause, H. Brendan Mcmahan, Google Inc, Carlos Guestrin, Anupam Gupta
In many applications, one has to actively select among a set of expensive observations before making an informed decision. Often, we want to select observations which perform well when evaluated with...
All-norms and all-Lp-norms approximation algorithms (2007)
Daniel Golovin, Anupam Gupta, Amit Kumar, Kanat Tangwongsan
ABSTRACT. In many optimization problems, a solution can be viewed as ascribing a “cost ” to each client, and the goal is to optimize some aggregation of the per-client costs. We often optimize...
Metric Embeddings with Relaxed Guarantees (2006)
Chan, T-H. Hubert, Dhamdhere, Kedar, Gupta, Anupam, Kleinberg, Jon, Slivkins, Aleksandrs Aleksandrs Slivkins
We consider the problem of embedding finite metrics with "slack": we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be...
Metric Embeddings with Relaxed Guarantees (2006)
Chan, T-H. Hubert, Dhamdhere, Kedar, Gupta, Anupam, Kleinberg, Jon, Slivkins, Aleksandrs Aleksandrs Slivkins
We consider the problem of embedding finite metrics with "slack": we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be...
Improved embeddings of graph metrics into random trees (2006)
Kedar Dhamdhere, Anupam Gupta, Harald Räcke
Over the past decade, numerous algorithms have been developed using the fact that the distances in any n-point metric (V, d) can be approximated to within O(log n) by distributions D over trees on...
Anupam Gupta, Aravind Srinivasan
Abstract: In the Covering Steiner problem, we are given an undirected graph with edgecosts, and some subsets of vertices called groups, with each group being equipped with a non-negative integer...
Near-optimal sensor placements: Maximizing information while minimizing communication cost (2006)
When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a fundamental task. Not only should the sensors be informative, but they should also be able...
Improved embeddings of graph metrics into random trees (2006)
Abstract Over the past decade, numerous algorithms have beendeveloped using the fact that the distances in any n-point metric (V, d) can be approximated to within O(log n) by distributions D over...
Thesis Proposal Towards a More Principled Compiler: Progressive Backend Compiler Optimization (2006)
David Ryan Koes, Peter Lee, Anupam Gupta, Michael D. Smith
As we reach the limits of processor performance and architectural complexity increases, more principled approaches to compiler optimization are necessary to fully exploit the performance potential of...
Abstract. Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion. In this paper, we study the problem of...
Quorum placement in networks: Minimizing network congestion (2006)
Daniel Golovin, Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter
A quorum system over a universe of logical elements is a collection of subsets (quorums) of elements, any two of which intersect. In numerous distributed algorithms, the elements of the universe...
Quorum placement in networks: Minimizing network congestion (2006)
Daniel Golovin, Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter
A quorum system over a universe of logical elements is a collection of subsets (quorums) of elements, any two of which intersect. In numerous distributed algorithms, the elements of the universe...
Quorum Placement in Networks: Minimizing Network Congestion (2006)
Daniel Golovin, Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter
A quorum system over a universe of logical elements is a collection of subsets (quorums) of elements, any two of which intersect. In numerous distributed algorithms, the elements of the universe...
Near-optimal Sensor Placements: (2006)
Maximizing Information While, Andreas Krause, Anupam Gupta
When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a fundamental task. Not only should the sensors be informative, but they should also be able...
Improved Embeddings of Graph Metrics into Random Trees (2006)
Kedar Dhamdhere Anupam, Anupam Gupta, Harald Räcke
Over the past decade, numerous algorithms have been developed using the fact that the distances in any n-point metric (V, d) can be approximated to within O(log n) by distributions over trees on the...
Oblivious network design (2006)
Anupam Gupta, Mohammad T. Hajiaghayi, Harald Räcke
Consider the following network design problem: given a network G = (V, E), source-sink pairs {si, ti} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if...
On the Covering Steiner Problem (2006)
Anupam Gupta, Aravind Srinivasan
Abstract. The Covering Steiner problem is a common generalization of the k-MST and Group Steiner problems. An instance of the Covering Steiner problem consists of an undirected graph with edge-costs,...
Near-optimal sensor placements: Maximizing information while minimizing communication cost (2006)
Andreas Krause, Anupam Gupta, Carlos Guestrin, Jon Kleinberg
When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a fundamental task. Not only should the sensors be informative, but they should also be able...
Quorum placement in networks: Minimizing network congestion (2006)
Daniel Golovin, Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter
Oblivious network design (2006)
Anupam Gupta, Mohammad T. Hajiaghayi, Harald Räcke
Consider the following network design problem: given a network G = (V, E), source-sink pairs {si, ti} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if...
Small hop-diameter sparse spanners for doubling metrics (2006)
Given a metric M = (V, d), a graph G = (V, E) is a t-spanner for M if every pair of nodes in V has a “short ” path (i.e., of length at most t times their actual distance) between them in the...
Oblivious network design (2006)
Anupam Gupta, Mohammad T. Hajiaghayi, Harald Räcke
Consider the following network design problem: given a network G = (V, E), source-sink pairs {si, ti} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if...
Approximating unique games (2006)
The Unique Games problem is the following: we are given a graph G = (V, E), with each edge e = (u, v) having a weight we and a permutation πuv on [k]. The objective is to find a labeling of each...
LP Rounding Approximation Algorithms for Stochastic Network Design (2006)
Anupam Gupta, R. Ravi, Amitabh Sinha
doi 10.1287/moor.1060.0237
Quorum placement in networks to minimize access delays (2005)
Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Anastasios Sidiropoulos
Abstract We present several approximation algorithms for theproblem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, wegive an O(pn)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Abstract We present constant-factor approximation algorithms for several widely-studied NP-hard optimization problems in network design, including the multicommodity rentor-buy, virtual private...
Graph Algorithms for Planning and Partitioning (2005)
Shuchi Chawla, Anupam Gupta, R. Ravi
In this thesis, we present new approximation algorithms as well as hardness of approximation results for several planning and partitioning problems. In planning problems, one is typically given a set...
Quorum Placement in Networks to Minimize Access Delays (2005)
Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter
A quorum system is a family of sets (themselves called quorums) , each pair of which intersect. In many distributed algorithms, the basic unit accessed by a client is a quorum of nodes. Such...
On Hierarchical Routing in Doubling Metrics (2005)
Hubert Chan Anupam, Anupam Gupta
We study the problem of routing in doubling metrics, and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with small amount of routing...
Approximation Algorithms for Low-Distortion Embeddings Into (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O( # n)-approximation algorithm...
Graph Algorithms for Planning and Partitioning (2005)
Shuchi Chawla, Anupam Gupta, R. Ravi
official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other entity.
Approximation Algorithms for Metric Embedding Problems (2005)
We initiate the study of metric embedding problems from an approximation point of view. Metric embedding is a map from a guest metric to a host metric. The quality of the embedding is defined in...
On hierarchical routing in doubling metrics (2005)
Anupam Gupta, Bruce M. Maggs, Shuheng Zhou
We study the problem of routing in doubling metrics, and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing...
What about Wednesday? approximation algorithms for multistage stochastic optimization (2005)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Abstract. The field of stochastic optimization studies decision making under uncertainty, when only probabilistic information about the future is available. Finding approximate solutions to...
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut (2005)
Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V,d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2squared” metrics. We show how to...
Boosted sampling: Approximation algorithms for stochastic optimization (2004)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. For example, in the STEINER TREE...
Approximation algorithms for minimizing average distortion (2004)
Kedar Dhamdhere, Anupam Gupta, R. Ravi
Abstract This paper considers embeddings f of arbitrary finite metrics into the line metric! so thatnone of the distances is shrunk by the embedding f; the quantity of interest is the factor by...
A.: Boosted sampling: Approximation algorithms for stochastic optimization problems (2004)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem, for...
An elementary proof of a theorem of (2003)
ABSTRACT: A result of Johnson and Lindenstrauss [13] shows that a set of n points in high dimensional Euclidean space can be mapped into an O(log n/ � 2)-dimensional Euclidean space such that the...
Exploring the trade-off between label size and stack depth (2003)
is being increasingly deployed by several of the largest Internet service providers to solve problems such as traffic engineering and to offer IP services like Virtual Private Networks (VPNs). In...
Bounded geometries, fractals, and low-distortion embeddings (2003)
Anupam Gupta, Robert Krauthgamer, James R. Lee
The doubling constant of a metric space (X, d) is the smallest value # such that every ball in X can be covered by # balls of half the radius. The doubling dimension of X is then defined as dim(X) =...
Anupam Gupta, Amit Kumar, Martin Pal, Tim Roughgarden
We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of...
Simpler and Better Approximation Algorithms for Network Design (2003)
Anupam Gupta, Amit Kumar, Tim Roughgarden
We give simple and easy-to-analyze randomized approximation algorithms for several well-studied NP-hard network design problems. Our algorithms improve over the previously best known approximation...
Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden
We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of...
Bounded geometries, fractals, and low-distortion embeddings (2003)
Anupam Gupta, Robert Krauthgamer, James R. Lee
Abstract The doubling constant of a metric space (X, d) is thesmallest value * such that every ball in X can be covered by * balls of half the radius. The doubling dimension of X isthen defined as...
Boosted Sampling: Approximation Algorithms for Stochastic Optimization (2003)
Anupam Gupta, Martin Pal, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. For example, in the STEINER TREE...
Improved results for directed multicut (2003)
We give a simple algorithm for the MINIMUM DIRECT-ED MULTICUT problem, and show that it gives an-approximation. This improves on the previous approximation guarantee of ��of Cheriyan, Karloff and...
Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden
We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of...
Counting inversions in lists (2003)
issues we face here. In a recent paper, Ajtai et al. [1] give a streaming algorithm In the rest of the paper, , where is the to count the number of inversions in a stream �℄using allowed error....
Simpler and better approximation algorithms for network design (2003)
Anupam Gupta, Amit Kumar, Tim Roughgarden
We give simple and easy-to-analyze randomized approximation algorithms for several well-studied NP-hard network design problems. Our algorithms improve over the previously best known approximation...
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem (2002)
In a traditional classification problem, we wish to assign labels from a set L to each of n objects so that the labeling is consistent with some observed data that includes pairwise relationships...
A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem (2002)
Amit Kumar, Anupam Gupta, Tim Roughgarden
We present the first constant-factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity...
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem (2002)
Amit Kumar, Anupam Gupta, Tim Roughgarden
We present the first constant-factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity...
A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem (2002)
Amit Kumar, Anupam Gupta, Tim Roughgarden
We present the first constant-factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity...
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem (2002)
Amit Kumar, Anupam Gupta, Tim Roughgarden
We present the first constant-factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity...
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem (2002)
In a traditional classification problem, we wish to assign labels from a set to each of objects so that the labeling is consistent with some observed data that includes pairwise relationships among...
Provisioning a virtual private network: A network design problem for multicommodity flow (2001)
Anupam Gupta, Jon Kleinberg, Amit Kumar, Rajeev Rastogi, Bulent Yener
Consider a setting in which a group of nodes, situated in a large underlying network, wishes to reserve bandwidth on which to support communication. Virtual private networks (VPNs) are services that...
Sorting and Selection with Structured Costs (2001)
The (unit-cost) comparison tree model has long been the basis of evaluating the performance of algorithms for fundamental problems like sorting and searching. In this model, the assumption is that...
Provisioning a Virtual Private Network: A network design problem for multicommodity flow (2001)
Anupam Gupta, Jon Kleinberg, Amit Kumar, Rajeev Rastogi, Bulent Yener
Consider a setting in which a group of nodes, situated in a large underlying network, wishes to reserve bandwidth on which to support communication. Virtual private networks (VPNs) are services that...
Embeddings of finite metrics /--by Anupam Gupta. (2000)
Thesis (Ph. D. in Computer Science)--University of California, Berkeley, Fall 2000.
Embedding tree metrics into low dimensional Euclidean spaces (2000)
We consider the question of embedding metrics induced by trees into Euclidean spaces with a restricted number of dimensions. We show that any weighted tree T with n(T ) vertices and l(T ) leaves can...
Improved bandwidth approximation for trees (2000)
A linear arrangement of an n-vertex graph G = (V; E) is a one-one mapping f of the vertex set V onto the set [n] = f0; 1; : : : ; n 1g. The bandwidth of this linear arrangement is the maximum...
An elementary proof of the Johnson-Lindenstrauss Lemma (1999)
Sanjoy Dasgupta Anupam, Anupam Gupta
The Johnson-Lindenstrauss lemma shows that a set of n points in high dimensional Euclidean space can be mapped down into an O(log n=ffl 2 ) dimensional Euclidean space such that the distance between...
An elementary proof of the Johnson-Lindenstrauss Lemma (1999)
The Johnson-Lindenstrauss lemma shows that a set of n points in high dimensional Euclidean space can be mapped down into an O(log n=ffl 2 ) dimensional Euclidean space such that the distance between...
Quality of life and psychological problems in patients undergoing neurological rehabilitation
Gupta, Anupam, Deepika, S., Taly, A. B., Srivastava, Abhishek, Surender, Vishal, Thyloth, Murali
Catatonia and multiple pressure ulcers: A rare complication in psychiatric setting
Srivastava, Abhishek, Gupta, Anupam, Murthy, Pratima, Murali, Thyloth
The incidence of pressure ulcers in patients with psychiatric illness, especially with catatonia might be more than what is reported in the literature. We report a case of catatonia secondary to...