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 |