dblp.uni-trier.dewww.uni-trier.de

Anupam Gupta

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

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

Coauthor Index

1Ittai Abraham [39]
2Alexandr Andoni [18]
3Barbara M. Anthony [58] [73]
4Moshe Babaioff [80]
5Mihai Badoiu [35]
6Maria-Florina Balcan (Maria-Florina Popa) [81]
7Nikhil Bansal [59]
8Ziv Bar-Joseph [64]
9Yair Bartal [39]
10Avrim Blum [81]
11Yuri Breitbart [62]
12Niv Buchbinder [59]
13Amit Chakrabarti [13] [55]
14T.-H. Hubert Chan (Hubert T.-H. Chan) [34] [39] [47] [51] [70] [72] [77] [78]
15Shuchi Chawla [36] [68]
16Chandra Chekuri [11] [13] [17] [31] [32] [44] [55] [71]
17Julia Chuzhoy [33] [67]
18Sanjoy Dasgupta [14]
19Michel Deza [18]
20Kedar Dhamdhere [28] [35] [39] [43] [48] [77]
21Michael Dinitz [51] [80]
22Guy Even [71]
23Naveen Garg [69]
24Minos N. Garofalakis [62]
25Daniel Golovin [49] [75]
26Vineet Goyal [60] [73]
27Fabrizio Grandoni [76]
28Carlos Guestrin [50] [57]
29Mohammad Taghi Hajiaghayi (MohammadTaghi Hajiaghayi) [46] [54] [61] [63]
30Nicole Immorlica [80]
31Piotr Indyk [18]
32Jon M. Kleinberg [7] [39] [50] [77]
33Jochen Könemann [56]
34Andreas Krause [50] [57]
35Robert Krauthgamer [24]
36Amit Kumar [7] [9] [10] [11] [12] [13] [15] [16] [21] [23] [25] [31] [32] [41] [52] [55] [62] [63] [75]
37James R. Lee [24]
38Stefano Leonardi [56] [60] [69] [76]
39Katrina Ligett [79]
40Bruce M. Maggs [34] [37] [49]
41H. Brendan McMahan [57]
42Frank McSherry [79]
43Pauli Miettinen [76]
44Viswanath Nagarajan [54] [61] [73]
45Joseph Naor (Seffi Naor) [11] [32] [33] [59] [67]
46Ofer Neiman [39]
47Ilan Newman [2] [17] [26] [44]
48Florian Oprea [37] [49]
49Martin Pál (Martin Pal) [23] [27] [38] [40] [52]
50Yuri Rabinovich [2] [17] [26] [35] [44]
51Harald Räcke [35] [36] [46] [48] [68]
52Sofya Raskhodnikova [18]
53Rajeev Rastogi [7] [10] [21] [25] [62]
54R. Ravi [27] [28] [29] [35] [40] [43] [54] [56] [60] [61]
55Danny Raz [11] [32]
56Michael K. Reiter [37] [49]
57Aaron Roth [79]
58Tim Roughgarden [12] [15] [23] [52]
59Piotr Sankowski [69] [76]
60Guido Schäfer [56]
61Danny Segev [71]
62Anastasios Sidiropoulos [35]
63Alistair Sinclair [2] [17] [26] [44]
64Mohit Singh [76]
65Amitabh Sinha [27] [29] [33] [40] [67]
66Aleksandrs Slivkins [39] [77]
67Aravind Srinivasan [22] [30] [42] [66]
68Kunal Talwar [45] [53] [72] [74] [79] [80]
69Kanat Tangwongsan [65] [75]
70Éva Tardos [4] [30] [66]
71Mikkel Thorup [16]
72Bülent Yener [7]
73Francis Zane [20]
74Shuheng Zhou [34]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)