| 2009 |
|---|
| 81 | EE | Maria-Florina Balcan,
Avrim Blum,
Anupam Gupta:
Approximate clustering without the approximation.
SODA 2009: 1068-1077 |
| 80 | EE | Moshe Babaioff,
Michael Dinitz,
Anupam Gupta,
Nicole Immorlica,
Kunal Talwar:
Secretary problems: weights and discounts.
SODA 2009: 1245-1254 |
| 79 | EE | Anupam Gupta,
Katrina Ligett,
Frank McSherry,
Aaron Roth,
Kunal Talwar:
Differentially Private Approximation Algorithms
CoRR abs/0903.4510: (2009) |
| 78 | EE | T.-H. Hubert Chan,
Anupam Gupta:
Small Hop-diameter Sparse Spanners for Doubling Metrics.
Discrete & Computational Geometry 41(1): 28-44 (2009) |
| 77 | EE | T.-H. Hubert Chan,
Kedar Dhamdhere,
Anupam Gupta,
Jon M. Kleinberg,
Aleksandrs Slivkins:
Metric Embeddings with Relaxed Guarantees.
SIAM J. Comput. 38(6): 2303-2329 (2009) |
| 2008 |
|---|
| 76 | EE | Fabrizio Grandoni,
Anupam Gupta,
Stefano Leonardi,
Pauli Miettinen,
Piotr Sankowski,
Mohit Singh:
Set Covering with our Eyes Closed.
FOCS 2008: 347-356 |
| 75 | EE | Daniel Golovin,
Anupam Gupta,
Amit Kumar,
Kanat Tangwongsan:
All-Norms and All-L_p-Norms Approximation Algorithms.
FSTTCS 2008 |
| 74 | EE | Anupam Gupta,
Kunal Talwar:
How to Complete a Doubling Metric.
LATIN 2008: 36-47 |
| 73 | EE | Barbara M. Anthony,
Vineet Goyal,
Anupam Gupta,
Viswanath Nagarajan:
A plant location guide for the unsure.
SODA 2008: 1164-1173 |
| 72 | EE | T.-H. Hubert Chan,
Anupam Gupta,
Kunal Talwar:
Ultra-low-dimensional embeddings for doubling metrics.
SODA 2008: 333-342 |
| 71 | EE | Chandra Chekuri,
Guy Even,
Anupam Gupta,
Danny Segev:
Set connectivity problems in undirected graphs and the directed Steiner network problem.
SODA 2008: 532-541 |
| 70 | EE | T.-H. Hubert Chan,
Anupam Gupta:
Approximating TSP on metrics with bounded global growth.
SODA 2008: 690-699 |
| 69 | EE | Naveen Garg,
Anupam Gupta,
Stefano Leonardi,
Piotr Sankowski:
Stochastic analyses for online combinatorial optimization problems.
SODA 2008: 942-951 |
| 68 | EE | Shuchi Chawla,
Anupam Gupta,
Harald Räcke:
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.
ACM Transactions on Algorithms 4(2): (2008) |
| 67 | EE | Julia Chuzhoy,
Anupam Gupta,
Joseph Naor,
Amitabh Sinha:
On the approximability of some network design problems.
ACM Transactions on Algorithms 4(2): (2008) |
| 66 | EE | Anupam Gupta,
Aravind Srinivasan,
Éva Tardos:
Cost-Sharing Mechanisms for Network Design.
Algorithmica 50(1): 98-119 (2008) |
| 65 | EE | Anupam Gupta,
Kanat Tangwongsan:
Simpler Analyses of Local Search Algorithms for Facility Location
CoRR abs/0809.2554: (2008) |
| 64 | EE | Anupam Gupta,
Ziv Bar-Joseph:
Extracting Dynamics from Static Cancer Expression Data.
IEEE/ACM Trans. Comput. Biology Bioinform. 5(2): 172-182 (2008) |
| 2007 |
|---|
| 63 | EE | Anupam Gupta,
MohammadTaghi Hajiaghayi,
Amit Kumar:
Stochastic Steiner Tree with Non-uniform Inflation.
APPROX-RANDOM 2007: 134-148 |
| 62 | EE | Yuri Breitbart,
Minos N. Garofalakis,
Anupam Gupta,
Amit Kumar,
Rajeev Rastogi:
On Configuring BGP Route Reflectors.
COMSWARE 2007 |
| 61 | EE | Anupam Gupta,
MohammadTaghi Hajiaghayi,
Viswanath Nagarajan,
R. Ravi:
Dial a Ride from k -Forest.
ESA 2007: 241-252 |
| 60 | EE | Vineet Goyal,
Anupam Gupta,
Stefano Leonardi,
R. Ravi:
Pricing Tree Access Networks with Connected Backbones.
ESA 2007: 498-509 |
| 59 | EE | Nikhil Bansal,
Niv Buchbinder,
Anupam Gupta,
Joseph Naor:
An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching.
ESA 2007: 522-533 |
| 58 | EE | Barbara M. Anthony,
Anupam Gupta:
Infrastructure Leasing Problems.
IPCO 2007: 424-438 |
| 57 | EE | Andreas Krause,
H. Brendan McMahan,
Carlos Guestrin,
Anupam Gupta:
Selecting Observations against Adversarial Objectives.
NIPS 2007 |
| 56 | EE | Anupam Gupta,
Jochen Könemann,
Stefano Leonardi,
R. Ravi,
Guido Schäfer:
An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem.
SODA 2007: 1153-1162 |
| 55 | EE | Amit Chakrabarti,
Chandra Chekuri,
Anupam Gupta,
Amit Kumar:
Approximation Algorithms for the Unsplittable Flow Problem.
Algorithmica 47(1): 53-78 (2007) |
| 54 | EE | Anupam Gupta,
MohammadTaghi Hajiaghayi,
Viswanath Nagarajan,
R. Ravi:
Dial a Ride from k-forest
CoRR abs/0707.0648: (2007) |
| 53 | EE | Anupam Gupta,
Kunal Talwar:
How to Complete a Doubling Metric
CoRR abs/0712.3331: (2007) |
| 52 | EE | Anupam Gupta,
Amit Kumar,
Martin Pál,
Tim Roughgarden:
Approximation via cost sharing: Simpler and better approximation algorithms for network design.
J. ACM 54(3): 11 (2007) |
| 2006 |
|---|
| 51 | EE | Hubert T.-H. Chan,
Michael Dinitz,
Anupam Gupta:
Spanners with Slack.
ESA 2006: 196-207 |
| 50 | EE | Andreas Krause,
Carlos Guestrin,
Anupam Gupta,
Jon M. Kleinberg:
Near-optimal sensor placements: maximizing information while minimizing communication cost.
IPSN 2006: 2-10 |
| 49 | EE | Daniel Golovin,
Anupam Gupta,
Bruce M. Maggs,
Florian Oprea,
Michael K. Reiter:
Quorum placement in networks: minimizing network congestion.
PODC 2006: 16-25 |
| 48 | EE | Kedar Dhamdhere,
Anupam Gupta,
Harald Räcke:
Improved embeddings of graph metrics into random trees.
SODA 2006: 61-69 |
| 47 | EE | Hubert T.-H. Chan,
Anupam Gupta:
Small hop-diameter sparse spanners for doubling metrics.
SODA 2006: 70-78 |
| 46 | EE | Anupam Gupta,
Mohammad Taghi Hajiaghayi,
Harald Räcke:
Oblivious network design.
SODA 2006: 970-979 |
| 45 | EE | Anupam Gupta,
Kunal Talwar:
Approximating unique games.
SODA 2006: 99-106 |
| 44 | EE | Chandra Chekuri,
Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Embedding k-Outerplanar Graphs into l 1.
SIAM J. Discrete Math. 20(1): 119-136 (2006) |
| 43 | EE | Kedar Dhamdhere,
Anupam Gupta,
R. Ravi:
Approximation Algorithms for Minimizing Average Distortion.
Theory Comput. Syst. 39(1): 93-111 (2006) |
| 42 | EE | Anupam Gupta,
Aravind Srinivasan:
An Improved Approximation Ratio for the Covering Steiner Problem.
Theory of Computing 2(1): 53-64 (2006) |
| 2005 |
|---|
| 41 | EE | Anupam Gupta,
Amit Kumar:
Where's the Winner? Max-Finding and Sorting with Metric Costs.
APPROX-RANDOM 2005: 74-85 |
| 40 | EE | Anupam Gupta,
Martin Pál,
R. Ravi,
Amitabh Sinha:
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization.
APPROX-RANDOM 2005: 86-98 |
| 39 | EE | Ittai Abraham,
Yair Bartal,
Hubert T.-H. Chan,
Kedar Dhamdhere,
Anupam Gupta,
Jon M. Kleinberg,
Ofer Neiman,
Aleksandrs Slivkins:
Metric Embeddings with Relaxed Guarantees.
FOCS 2005: 83-100 |
| 38 | EE | Anupam Gupta,
Martin Pál:
Stochastic Steiner Trees Without a Root.
ICALP 2005: 1051-1063 |
| 37 | EE | Anupam Gupta,
Bruce M. Maggs,
Florian Oprea,
Michael K. Reiter:
Quorum placement in networks to minimize access delays.
PODC 2005: 87-96 |
| 36 | EE | Shuchi Chawla,
Anupam Gupta,
Harald Räcke:
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.
SODA 2005: 102-111 |
| 35 | EE | Mihai Badoiu,
Kedar Dhamdhere,
Anupam Gupta,
Yuri Rabinovich,
Harald Räcke,
R. Ravi,
Anastasios Sidiropoulos:
Approximation algorithms for low-distortion embeddings into low-dimensional spaces.
SODA 2005: 119-128 |
| 34 | EE | Hubert T.-H. Chan,
Anupam Gupta,
Bruce M. Maggs,
Shuheng Zhou:
On hierarchical routing in doubling metrics.
SODA 2005: 762-771 |
| 33 | EE | Julia Chuzhoy,
Anupam Gupta,
Joseph Naor,
Amitabh Sinha:
On the approximability of some network design problems.
SODA 2005: 943-951 |
| 32 | EE | Chandra Chekuri,
Anupam Gupta,
Amit Kumar,
Joseph Naor,
Danny Raz:
Building Edge-Failure Resilient Networks.
Algorithmica 43(1-2): 17-41 (2005) |
| 31 | EE | Chandra Chekuri,
Anupam Gupta,
Amit Kumar:
On a bidirected relaxation for the MULTIWAY CUT problem.
Discrete Applied Mathematics 150(1-3): 67-79 (2005) |
| 2004 |
|---|
| 30 | EE | Anupam Gupta,
Aravind Srinivasan,
Éva Tardos:
Cost-Sharing Mechanisms for Network Design.
APPROX-RANDOM 2004: 139-150 |
| 29 | EE | Anupam Gupta,
R. Ravi,
Amitabh Sinha:
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
FOCS 2004: 218-227 |
| 28 | EE | Kedar Dhamdhere,
Anupam Gupta,
R. Ravi:
Approximation Algorithms for Minimizing Average Distortion.
STACS 2004: 234-245 |
| 27 | EE | Anupam Gupta,
Martin Pál,
R. Ravi,
Amitabh Sinha:
Boosted sampling: approximation algorithms for stochastic optimization.
STOC 2004: 417-426 |
| 26 | EE | Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs.
Combinatorica 24(2): 233-269 (2004) |
| 25 | EE | Anupam Gupta,
Amit Kumar,
Rajeev Rastogi:
Traveling with a Pez Dispenser (or, Routing Issues in MPLS).
SIAM J. Comput. 34(2): 453-474 (2004) |
| 2003 |
|---|
| 24 | EE | Anupam Gupta,
Robert Krauthgamer,
James R. Lee:
Bounded Geometries, Fractals, and Low-Distortion Embeddings.
FOCS 2003: 534-543 |
| 23 | EE | Anupam Gupta,
Amit Kumar,
Martin Pál,
Tim Roughgarden:
Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.
FOCS 2003: 606- |
| 22 | EE | Anupam Gupta,
Aravind Srinivasan:
On the Covering Steiner Problem.
FSTTCS 2003: 244-251 |
| 21 | EE | Anupam Gupta,
Amit Kumar,
Rajeev Rastogi:
Exploring the trade-off between label size and stack depth in MPLS Routing.
INFOCOM 2003 |
| 20 | EE | Anupam Gupta,
Francis Zane:
Counting inversions in lists.
SODA 2003: 253-254 |
| 19 | EE | Anupam Gupta:
Improved results for directed multicut.
SODA 2003: 454-455 |
| 18 | EE | Alexandr Andoni,
Michel Deza,
Anupam Gupta,
Piotr Indyk,
Sofya Raskhodnikova:
Lower bounds for embedding edit distance into normed spaces.
SODA 2003: 523-526 |
| 17 | EE | Chandra Chekuri,
Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Embedding k-outerplanar graphs into l1.
SODA 2003: 527-536 |
| 16 | EE | Anupam Gupta,
Amit Kumar,
Mikkel Thorup:
Tree based MPLS routing.
SPAA 2003: 193-199 |
| 15 | EE | Anupam Gupta,
Amit Kumar,
Tim Roughgarden:
Simpler and better approximation algorithms for network design.
STOC 2003: 365-372 |
| 14 | EE | Sanjoy Dasgupta,
Anupam Gupta:
An elementary proof of a theorem of Johnson and Lindenstrauss.
Random Struct. Algorithms 22(1): 60-65 (2003) |
| 2002 |
|---|
| 13 | EE | Amit Chakrabarti,
Chandra Chekuri,
Anupam Gupta,
Amit Kumar:
Approximation Algorithms for the Unsplittable Flow Problem.
APPROX 2002: 51-66 |
| 12 | EE | Amit Kumar,
Anupam Gupta,
Tim Roughgarden:
A Constant-Factor Approximation Algorithm for the Multicommodity.
FOCS 2002: 333- |
| 11 | EE | Chandra Chekuri,
Anupam Gupta,
Amit Kumar,
Joseph Naor,
Danny Raz:
Building Edge-Failure Resilient Networks.
IPCO 2002: 439-456 |
| 2001 |
|---|
| 10 | | Anupam Gupta,
Amit Kumar,
Rajeev Rastogi:
Traveling with a Pez Dispenser (Or, Routing Issues in MPLS).
FOCS 2001: 148-157 |
| 9 | | Anupam Gupta,
Amit Kumar:
Sorting and Selection with Structured Costs.
FOCS 2001: 416-425 |
| 8 | EE | Anupam Gupta:
Steiner points in tree metrics don't (really) help.
SODA 2001: 220-227 |
| 7 | EE | Anupam Gupta,
Jon M. Kleinberg,
Amit Kumar,
Rajeev Rastogi,
Bülent Yener:
Provisioning a virtual private network: a network design problem for multicommodity flow.
STOC 2001: 389-398 |
| 6 | | Anupam Gupta:
Improved Bandwidth Approximation for Trees and Chordal Graphs.
J. Algorithms 40(1): 24-36 (2001) |
| 2000 |
|---|
| 5 | EE | Anupam Gupta:
Improved bandwidth approximation for trees.
SODA 2000: 788-793 |
| 4 | EE | Anupam Gupta,
Éva Tardos:
A constant factor approximation algorithm for a class of classification problems.
STOC 2000: 652-658 |
| 3 | EE | Anupam Gupta:
Embedding Tree Metrics into Low-Dimensional Euclidean Spaces.
Discrete & Computational Geometry 24(1): 105-116 (2000) |
| 1999 |
|---|
| 2 | EE | Anupam Gupta,
Ilan Newman,
Yuri Rabinovich,
Alistair Sinclair:
Cuts, Trees and l1-Embeddings of Graphs.
FOCS 1999: 399-409 |
| 1 | EE | Anupam Gupta:
Embedding Tree Metrics Into Low Dimensional Euclidean Spaces.
STOC 1999: 694-700 |
