×

zbMATH — the first resource for mathematics

Gupta, Anupam

Compute Distance To:
Author ID: gupta.anupam Recent zbMATH articles by "Gupta, Anupam"
Published as: Gupta, Anupam; Gupta, A.
Homepage: http://www.cs.cmu.edu/~anupamg/
External Links: MGP · Google Scholar · dblp
Documents Indexed: 164 Publications since 1999
1 Contribution as Editor
all top 5

Co-Authors

6 single-authored
27 Kumar, Amit
27 Nagarajan, Viswanath
27 Ravi, Ramamoorthi
15 Krishnaswamy, Ravishankar
14 Talwar, Kunal
10 Bansal, Nikhil
9 Chan, T.-H. Hubert
9 Chekuri, Chandra S.
8 Racke, Harald
7 Naor, Joseph Seffi
6 Dhamdhere, Kedar
5 Guruganesh, Guru Prashanth
5 Leonardi, Stefano
5 Li, Jason Jingshi
5 Molinaro, Marco
5 Pál, Martin
5 Pruhs, Kirk R.
5 Rabinovich, Yuri
5 Sinha, Amitabh
4 Hajiaghayi, Mohammad Taghi
4 Lee, Euiwoong
4 Maggs, Bruce M.
4 Roth, Aaron Leon
4 Srinivasan, Aravind
3 Abraham, Ittai
3 Anthony, Barbara M.
3 Blum, Avrim L.
3 Buchbinder, Niv
3 Dinitz, Michael H.
3 Englert, Matthias
3 Goyal, Vineet
3 Krauthgamer, Robert
3 Neiman, Ofer
3 Newman, Ilan I.
3 Panigrahi, Debmalya
3 Sankowski, Piotr
3 Segev, Danny
3 Sidiropoulos, Anastasios
3 Sinclair, Alistair
3 Singh, Mohit
3 Singla, Sahil
3 Stein, Clifford
3 Tardos, Éva
3 Ullman, Jonathan R.
2 Andoni, Alexandr
2 Argue, C. J.
2 Babenko, Maxim A.
2 Bădoiu, Mihai
2 Balcan, Maria-Florina
2 Chakrabarti, Amit
2 Chawla, Shuchi
2 Chuzhoy, Julia
2 Even, Guy
2 Friggstad, Zachary
2 Gavoille, Cyril
2 Goldberg, Andrew V.
2 Golovin, Daniel
2 Gu, Albert
2 Guestrin, Carlos
2 Hardt, Moritz
2 Indyk, Piotr
2 Kleinberg, Jon Michael
2 Könemann, Jochen
2 Krause, Andreas
2 Mestre, Julián
2 Oprea, Florian
2 Rastogi, Rajeev
2 Raz, Danny
2 Reiter, Michael K.
2 Roughgarden, Tim
2 Rudra, Atri
2 Schafer, Guido
2 Schmidt, Melanie
2 Shen, Xiangkun
2 Talgam-Cohen, Inbal
2 Tangwongsan, Kanat
2 Zhou, Shuheng
1 Babaioff, Moshe
1 Bahga, Supreet S.
1 Blelloch, Guy E.
1 Bubeck, Sébastien
1 Chan, Hubert T-H.
1 Cohen, Michael B.
1 Cygan, Marek
1 Dasgupta, Sanjoy
1 Deza, Michel Marie
1 Feldkord, Björn
1 Feldotto, Matthias
1 Filtser, Arnold
1 Garg, Naveen Kumar
1 Grandoni, Fabrizio
1 Groß, Martin
1 Gu, Haijie
1 Im, Sungjin
1 Immorlica, Nicole
1 Jansen, Klaus
1 Jiang, Haotian
1 Kale, Satyen
1 Karandikar, Archit
1 Koutis, Ioannis
...and 44 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

136 Publications have been cited 1,145 times in 800 Documents Cited by Year
Privately releasing conjunctions and the statistical query barrier. Zbl 1288.68141
Gupta, Anupam; Hardt, Moritz; Roth, Aaron; Ullman, Jonathan
104
2011
Iterative constructions and private data release. Zbl 1304.68042
Gupta, Anupam; Roth, Aaron; Ullman, Jonathan
99
2012
An elementary proof of a theorem of Johnson and Lindenstrauss. Zbl 1018.51010
Dasgupta, Sanjoy; Gupta, Anupam
83
2003
Provisioning a virtual private network: a network design problem for multicommodity flow. Zbl 1323.68014
Gupta, Anupam; Kleinberg, Jon; Kumar, Amit; Rastogi, Rajeev; Yener, Bulent
46
2001
Simpler and better approximation algorithms for network design. Zbl 1192.90226
Gupta, Anupam; Kumar, Amit; Roughgarden, Tim
28
2003
Cuts, trees and \(\ell_1\)-embeddings of graphs. Zbl 1056.05040
Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair
28
2004
Steiner points in tree metrics don’t (really) help. Zbl 0990.05033
Gupta, Anupam
23
2001
Approximation algorithms for correlated knapsacks and non-martingale bandits. Zbl 1292.90216
Gupta, Anupam; Krishnaswamy, Ravishankar; Molinaro, Marco; Ravi, Ramamoorthi
19
2011
Approximation algorithms for low-distortion embeddings into low-dimensional spaces. Zbl 1297.68229
Bǎdoiu, Mihai; Dhamdhere, Kedar; Gupta, Anupam; Rabinovich, Yuri; Räcke, Harald; Ravi, R.; Sidiropoulos, Anastasios
19
2005
On hierarchical routing in doubling metrics. Zbl 1297.68090
Chan, Hubert T-H.; Gupta, Anupam; Maggs, Bruce M.; Zhou, Shuheng
18
2005
Approximation algorithms for the unsplittable flow problem. Zbl 1107.68120
Chakrabarti, Amit; Chekuri, Chandra; Gupta, Anupam; Kumar, Amit
18
2007
Boosted sampling: approximation algorithms for stochastic optimization. Zbl 1192.90171
Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha Amitabh
16
2004
Approximation via cost sharing: simpler and better approximation algorithms for network design. Zbl 1216.68339
Gupta, Anupam; Kumar, Amit; Pál, Martin; Roughgarden, Tim
16
2007
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. Zbl 1297.68234
Chawla, Shuchi; Gupta, Anupam; Räcke, Harald
15
2005
When LP is the cure for your matching woes: improved bounds for stochastic matchings. Zbl 1254.05145
Bansal, Nikhil; Gupta, Anupam; Li, Jian; Mestre, Julián; Nagarajan, Viswanath; Rudra, Atri
15
2012
Stochastic analyses for online combinatorial optimization problems. Zbl 1192.90169
Garg, Naveen; Gupta, Anupam; Leonardi, Stefano; Sankowski, Piotr
14
2008
A stochastic probing problem with applications. Zbl 1372.90091
Gupta, Anupam; Nagarajan, Viswanath
14
2013
Traveling with a pez dispenser (or, routing issues in MPLS). Zbl 1087.68013
Gupta, Anupam; Kumar, Amit; Rastogi, Rajeev
13
2005
Forest density estimation. Zbl 1280.62045
Liu, Han; Xu, Min; Gu, Haijie; Gupta, Anupam; Lafferty, John; Wasserman, Larry
13
2011
Online primal-dual for non-linear optimization with applications to speed scaling. Zbl 1394.68447
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
12
2013
Oblivious network design. Zbl 1192.68037
Gupta, Anupam; Hajiaghayi, Mohammad T.; Räcke, Harald
11
2006
Sparsest cut on bounded treewidth graphs: algorithms and hardness results. Zbl 1293.05042
Gupta, Anupam; Talwar, Kunal; Witmer, David
11
2013
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1295.68211
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
11
2011
Improved results for directed multicut. Zbl 1092.68627
Gupta, Anupam
11
2003
Scalably scheduling power-heterogeneous processors. Zbl 1288.68033
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
11
2010
A constant factor approximation algorithm for generalized MIN-sum set cover. Zbl 1288.68254
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar
11
2010
Approximation algorithms for VRP with stochastic demands. Zbl 1247.90050
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
11
2012
Packing interdiction and partial covering problems. Zbl 1372.90110
Dinitz, Michael; Gupta, Anupam
11
2013
Infrastructure leasing problems. Zbl 1136.90447
Anthony, Barbara M.; Gupta, Anupam
10
2007
Improved bandwidth approximation for trees and chordal graphs. Zbl 0979.68066
Gupta, Anupam
10
2001
Approximation algorithms for optimal decision trees and adaptive TSP problems. Zbl 1288.68267
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
10
2010
Cost-sharing mechanisms for network design. Zbl 1169.68314
Gupta, Anupam; Srinivasan, Aravind; Tardos, Éva
10
2008
Robust submodular observation selection. Zbl 1225.90107
Krause, Andreas; Mcmahan, H. Brendan; Guestrin, Carlos; Gupta, Anupam
10
2008
Vertex sparsifiers: new results from old techniques. Zbl 1302.90234
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
9
2014
Spanners with slack. Zbl 1131.68482
Chan, T.-H. Hubert; Dinitz, Michael; Gupta, Anupam
9
2006
Cost-sharing mechanisms for network design. Zbl 1105.68304
Gupta, Anupam; Srinivasan, Aravind; Tardos, Éva
9
2004
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. Zbl 1315.05130
Abraham, Ittai; Gavoille, Cyril; Gupta, Anupam; Neiman, Ofer; Talwar, Kunal
9
2014
Approximating unique games. Zbl 1192.91012
Gupta, Anupam; Talwar, Kunal
8
2006
LP rounding approximation algorithms for stochastic network design. Zbl 1279.90030
Gupta, Anupam; Ravi, R.; Sinha, Amitabh
8
2007
Embedding \(k\)-outerplanar graphs into \(\ell_1\). Zbl 1111.05022
Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair
8
2006
An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem. Zbl 1302.90235
Gupta, A.; Könemann, J.; Leonardi, S.; Ravi, R.; Schäfer, G.
8
2007
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1293.05041
Gu, Albert; Gupta, Anupam; Kumar, Amit
7
2013
When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract). Zbl 1287.05111
Bansal, Nikhil; Gupta, Anupam; Li, Jian; Mestre, Julián; Nagarajan, Viswanath; Rudra, Atri
7
2010
An improved approximation algorithm for requirement cut. Zbl 1194.05146
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
7
2010
What about Wednesday? Approximation algorithms for multistage stochastic optimization. Zbl 1142.90461
Gupta, Anupam; Pál, Martin; Ravi, Ramamoorthi; Sinha, Amitabh
7
2005
Scheduling with outliers. Zbl 1255.90060
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Segev, Danny
7
2009
Greedy algorithms for Steiner forest. Zbl 1321.68504
Gupta, Anupam; Kumar, Amit
7
2015
All-norms and all-\(L_p\)-norms approximation algorithms. Zbl 1248.68558
Golovin, Daniel; Gupta, Anupam; Kumar, Amit; Tangwongsan, Kanat
7
2008
Clustering under approximation stability. Zbl 1281.68232
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
7
2013
Online and dynamic algorithms for set cover. Zbl 1370.90217
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Panigrahi, Debmalya
7
2017
Scheduling heterogeneous processors isn’t as easy as you think. Zbl 1421.68248
Gupta, Anupam; Im, Sungjin; Krishnaswamy, Ravishankar; Moseley, Benjamin; Pruhs, Kirk
6
2012
Secretary problems: weights and discounts. Zbl 1422.68336
Babaioff, Moshe; Dinitz, Michael; Gupta, Anupam; Immorlica, Nicole; Talwar, Kunal
6
2009
Small hop-diameter sparse spanners for doubling metrics. Zbl 1163.68039
Chan, T.-H. Hubert; Gupta, Anupam
6
2009
Changing bases: multistage optimization for matroids and matchings. Zbl 1423.90067
Gupta, Anupam; Talwar, Kunal; Wieder, Udi
6
2014
Welfare and profit maximization with production costs. Zbl 1292.91078
Blum, Avrim; Gupta, Anupam; Mansour, Yishay; Sharma, Ankit
6
2011
On the approximability of some network design problems. Zbl 1297.68019
Chuzhoy, Julia; Gupta, Anupam; Naor, Joseph (Seffi); Sinha, Amitabh
6
2005
Differentially private combinatorial optimization. Zbl 1288.94087
Gupta, Anupam; Ligett, Katrina; McSherry, Frank; Roth, Aaron; Talwar, Kunal
6
2010
Online Steiner tree with deletions. Zbl 1421.68249
Gupta, Anupam; Kumar, Amit
6
2014
Approximate clustering without the approximation. Zbl 1422.68287
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
5
2009
Lower bounds for embedding edit distance into normed spaces. Zbl 1092.68685
Andoni, A.; Deza, M.; Gupta, Anupam; Indyk, P.; Raskhodnikova, S.
5
2003
Vertex sparsifiers: new results from old techniques. Zbl 1302.90233
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
5
2010
Stochastic Steiner trees without a root. Zbl 1084.90034
Gupta, Anupam; Pál, Martin
5
2005
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1333.68301
Gu, Albert; Gupta, Anupam; Kumar, Amit
5
2016
Dial a ride from \(k\)-forest. Zbl 1151.68745
Gupta, Anupam; Hajiaghayi, MohammadTaghi; Nagarajan, Viswanath; Ravi, R.
5
2007
Sampling and cost-sharing: approximation algorithms for stochastic optimization problems. Zbl 1252.68352
Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha, Amitabh
5
2011
On the Lovász theta function for independent sets in sparse graphs. Zbl 1321.05176
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru
5
2015
Running errands in time: approximation algorithms for stochastic orienteering. Zbl 1328.90067
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
5
2015
Stochastic Steiner tree with non-uniform inflation. Zbl 1171.90484
Gupta, Anupam; Hajiaghayi, MohammadTaghi; Kumar, Amit
5
2007
Maintaining assignments online: matching, scheduling, and flows. Zbl 1421.68250
Gupta, Anupam; Kumar, Amit; Stein, Cliff
5
2014
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1192.68030
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
4
2008
Embedding tree metrics into low dimensional Euclidean spaces. Zbl 1345.05065
Gupta, Anupam
4
1999
Dial a ride from \(k\)-forest. Zbl 1300.90010
Gupta, Anupam; Hajiaghayi, Mohammadtaghi; Nagarajan, Viswanath; Ravi, R.
4
2010
Thresholded covering algorithms for robust and max-min optimization. Zbl 1297.05188
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
4
2014
Algorithms and adaptivity gaps for stochastic probing. Zbl 1415.90102
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
4
2016
Adaptivity gaps for stochastic probing: submodular and XOS functions. Zbl 1423.90159
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
4
2017
The online metric matching problem for doubling metrics. Zbl 1272.90068
Gupta, Anupam; Lewi, Kevin
4
2012
Set covering with our eyes closed. Zbl 1275.68158
Grandoni, Fabrizio; Gupta, Anupam; Leonardi, Stefano; Miettinen, Pauli; Sankowski, Piotr; Singh, Mohit
4
2013
Metric embeddings with relaxed guarantees. Zbl 1191.68348
Chan, T.-H. Hubert; Dhamdhere, Kedar; Gupta, Anupam; Kleinberg, Jon; Slivkins, Aleksandrs
4
2009
Approximation algorithms for the unsplittable flow problem. Zbl 1013.90112
Chakrabarti, Amit; Chekuri, Chandra; Gupta, Anupam; Kumar, Amit
4
2002
Embedding \(k\)-outerplanar graphs into \(\ell_1\). Zbl 1092.68619
Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair
4
2003
Thresholded covering algorithms for robust and max-min optimization. Zbl 1287.68180
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
4
2010
A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching. Zbl 1318.68200
Bansal, Nikhil; Buchbinder, Niv; Gupta, Anupam; Naor, Joseph (seffi)
4
2014
Online and stochastic survivable network design. Zbl 1304.68139
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
4
2009
An FPT algorithm beating 2-approximation for \(k\)-cut. Zbl 1403.68350
Gupta, Anupam; Lee, Euiwoong; Li, Jason
4
2018
Towards \((1 + \varepsilon)\)-approximate flow sparsifiers. Zbl 1422.68280
Andoni, Alexandr; Gupta, Anupam; Krauthgamer, Robert
4
2014
Robust and max-min optimization under matroid and knapsack uncertainty sets. Zbl 1398.68689
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
4
2016
On hierarchical routing in doubling metrics. Zbl 1445.68108
Chan, T.-H. Hubert; Gupta, Anupam; Maggs, Bruce M.; Zhou, Shuheng
4
2016
A 2-competitive algorithm for online convex optimization with switching costs. Zbl 1375.68222
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk; Schewior, Kevin; Stein, Cliff
4
2015
Small hop-diameter sparse spanners for doubling metrics. Zbl 1192.05037
Chan, T.-H. Hubert; Gupta, Anupam
3
2006
Approximation algorithms for stochastic orienteering. Zbl 1423.90106
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
3
2012
How experts can solve LPs online. Zbl 1425.90066
Gupta, Anupam; Molinaro, Marco
3
2014
LAST but not least: online spanners for buy-at-bulk. Zbl 1410.68298
Gupta, Anupam; Ravi, R.; Talwar, Kunal; Umboh, Seeun William
3
2017
Ultra-low-dimensional embeddings for doubling metrics. Zbl 1327.46026
Chan, T.-H. Hubert; Gupta, Anupam; Talwar, Kunal
3
2010
Embedding tree metrics into low-dimensional Euclidean spaces. Zbl 0977.68086
Gupta, Anupam
3
2000
Tree embeddings for two-edge-connected network design. Zbl 1288.68266
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
3
2010
Multicast routing for energy minimization using speed scaling. Zbl 1383.68009
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Pruhs, Kirk; Stein, Cliff
3
2012
Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Zbl 1314.68361
Blelloch, Guy E.; Gupta, Anupam; Koutis, Ioannis; Miller, Gary L.; Peng, Richard; Tangwongsan, Kanat
3
2014
A constant-factor approximation for stochastic Steiner forest. Zbl 1304.68217
Gupta, Anupam; Kumar, Amit
3
2009
Approximating TSP on metrics with bounded global growth. Zbl 1192.68874
Chan, T.-H. Hubert; Gupta, Anupam
2
2008
Ultra-low-dimensional embeddings for doubling metrics. Zbl 1192.68732
Chan, T.-H. Hubert; Gupta, Anupam; Talwar, Kunal
2
2008
Chasing convex bodies with linear competitive ratio. Zbl 07304116
Argue, C. J.; Gupta, Anupam; Guruganesh, Guru; Tang, Ziye
1
2020
The number of minimum \(k\)-cuts: improving the Karger-Stein bound. Zbl 1437.05222
Gupta, Anupam; Lee, Euiwoong; Li, Jason
2
2019
The Markovian price of information. Zbl 1436.90149
Gupta, Anupam; Jiang, Haotian; Scully, Ziv; Singla, Sahil
2
2019
Losing treewidth by separating subsets. Zbl 1432.68355
Gupta, Anupam; Lee, Euiwoong; Li, Jason; Manurangsi, Pasin; Włodarczyk, Michał
2
2019
A nearly-linear bound for chasing nested convex bodies. Zbl 1431.68115
Argue, C. J.; Bubeck, Sébastien; Cohen, Michael B.; Gupta, Anupam; Lee, Yin Tat
1
2019
Potential-function proofs for gradient methods. Zbl 07140481
Bansal, Nikhil; Gupta, Anupam
1
2019
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. Zbl 1432.05077
Abraham, Ittai; Gavoille, Cyril; Gupta, Anupam; Neiman, Ofer; Talwar, Kunal
1
2019
An FPT algorithm beating 2-approximation for \(k\)-cut. Zbl 1403.68350
Gupta, Anupam; Lee, Euiwoong; Li, Jason
4
2018
Fully-dynamic bin packing with little repacking. Zbl 07375978
Feldkord, Björn; Feldotto, Matthias; Gupta, Anupam; Guruganesh, Guru; Kumar, Amit; Riechers, Sören; Wajc, David
1
2018
Maximizing profit with convex costs in the random-order model. Zbl 07375998
Gupta, Anupam; Mehta, Ruta; Molinaro, Marco
1
2018
Online and dynamic algorithms for set cover. Zbl 1370.90217
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Panigrahi, Debmalya
7
2017
Adaptivity gaps for stochastic probing: submodular and XOS functions. Zbl 1423.90159
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
4
2017
LAST but not least: online spanners for buy-at-bulk. Zbl 1410.68298
Gupta, Anupam; Ravi, R.; Talwar, Kunal; Umboh, Seeun William
3
2017
Approximation algorithms for optimal decision trees and adaptive TSP problems. Zbl 1420.68236
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
1
2017
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1333.68301
Gu, Albert; Gupta, Anupam; Kumar, Amit
5
2016
Algorithms and adaptivity gaps for stochastic probing. Zbl 1415.90102
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
4
2016
Robust and max-min optimization under matroid and knapsack uncertainty sets. Zbl 1398.68689
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
4
2016
On hierarchical routing in doubling metrics. Zbl 1445.68108
Chan, T.-H. Hubert; Gupta, Anupam; Maggs, Bruce M.; Zhou, Shuheng
4
2016
An improved integrality gap for asymmetric TSP paths. Zbl 1371.90120
Friggstad, Zachary; Gupta, Anupam; Singh, Mohit
1
2016
How the experts algorithm can help solve LPs online. Zbl 1349.90604
Gupta, Anupam; Molinaro, Marco
1
2016
Greedy algorithms for Steiner forest. Zbl 1321.68504
Gupta, Anupam; Kumar, Amit
7
2015
On the Lovász theta function for independent sets in sparse graphs. Zbl 1321.05176
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru
5
2015
Running errands in time: approximation algorithms for stochastic orienteering. Zbl 1328.90067
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
5
2015
A 2-competitive algorithm for online convex optimization with switching costs. Zbl 1375.68222
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk; Schewior, Kevin; Stein, Cliff
4
2015
Efficient cost-sharing mechanisms for prize-collecting problems. Zbl 1319.90056
Gupta, A.; Könemann, Jochen; Leonardi, S.; Ravi, R.; Schäfer, G.
1
2015
Vertex sparsifiers: new results from old techniques. Zbl 1302.90234
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
9
2014
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. Zbl 1315.05130
Abraham, Ittai; Gavoille, Cyril; Gupta, Anupam; Neiman, Ofer; Talwar, Kunal
9
2014
Changing bases: multistage optimization for matroids and matchings. Zbl 1423.90067
Gupta, Anupam; Talwar, Kunal; Wieder, Udi
6
2014
Online Steiner tree with deletions. Zbl 1421.68249
Gupta, Anupam; Kumar, Amit
6
2014
Maintaining assignments online: matching, scheduling, and flows. Zbl 1421.68250
Gupta, Anupam; Kumar, Amit; Stein, Cliff
5
2014
Thresholded covering algorithms for robust and max-min optimization. Zbl 1297.05188
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
4
2014
A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching. Zbl 1318.68200
Bansal, Nikhil; Buchbinder, Niv; Gupta, Anupam; Naor, Joseph (seffi)
4
2014
Towards \((1 + \varepsilon)\)-approximate flow sparsifiers. Zbl 1422.68280
Andoni, Alexandr; Gupta, Anupam; Krauthgamer, Robert
4
2014
How experts can solve LPs online. Zbl 1425.90066
Gupta, Anupam; Molinaro, Marco
3
2014
Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Zbl 1314.68361
Blelloch, Guy E.; Gupta, Anupam; Koutis, Ioannis; Miller, Gary L.; Peng, Richard; Tangwongsan, Kanat
3
2014
Approximating sparse covering integer programs online. Zbl 1327.68338
Gupta, Anupam; Nagarajan, Viswanath
2
2014
A stochastic probing problem with applications. Zbl 1372.90091
Gupta, Anupam; Nagarajan, Viswanath
14
2013
Online primal-dual for non-linear optimization with applications to speed scaling. Zbl 1394.68447
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
12
2013
Sparsest cut on bounded treewidth graphs: algorithms and hardness results. Zbl 1293.05042
Gupta, Anupam; Talwar, Kunal; Witmer, David
11
2013
Packing interdiction and partial covering problems. Zbl 1372.90110
Dinitz, Michael; Gupta, Anupam
11
2013
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1293.05041
Gu, Albert; Gupta, Anupam; Kumar, Amit
7
2013
Clustering under approximation stability. Zbl 1281.68232
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
7
2013
Set covering with our eyes closed. Zbl 1275.68158
Grandoni, Fabrizio; Gupta, Anupam; Leonardi, Stefano; Miettinen, Pauli; Sankowski, Piotr; Singh, Mohit
4
2013
The approximability of the binary paintshop problem. Zbl 1407.68194
Gupta, Anupam; Kale, Satyen; Nagarajan, Viswanath; Saket, Rishi; Schieber, Baruch
2
2013
Algorithms for hub label optimization. Zbl 1336.68287
Babenko, Maxim; Goldberg, Andrew V.; Gupta, Anupam; Nagarajan, Viswanath
1
2013
Privately releasing conjunctions and the statistical query barrier. Zbl 1290.68062
Gupta, Anupam; Hardt, Moritz; Roth, Aaron; Ullman, Jonathan
1
2013
Thrifty algorithms for multistage robust optimization. Zbl 1372.90092
Gupta, Anupam; Nagarajan, Viswanath; Vazirani, Vijay V.
1
2013
Iterative constructions and private data release. Zbl 1304.68042
Gupta, Anupam; Roth, Aaron; Ullman, Jonathan
99
2012
When LP is the cure for your matching woes: improved bounds for stochastic matchings. Zbl 1254.05145
Bansal, Nikhil; Gupta, Anupam; Li, Jian; Mestre, Julián; Nagarajan, Viswanath; Rudra, Atri
15
2012
Approximation algorithms for VRP with stochastic demands. Zbl 1247.90050
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
11
2012
Scheduling heterogeneous processors isn’t as easy as you think. Zbl 1421.68248
Gupta, Anupam; Im, Sungjin; Krishnaswamy, Ravishankar; Moseley, Benjamin; Pruhs, Kirk
6
2012
The online metric matching problem for doubling metrics. Zbl 1272.90068
Gupta, Anupam; Lewi, Kevin
4
2012
Approximation algorithms for stochastic orienteering. Zbl 1423.90106
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
3
2012
Multicast routing for energy minimization using speed scaling. Zbl 1383.68009
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Pruhs, Kirk; Stein, Cliff
3
2012
Approximating TSP on metrics with bounded global growth. Zbl 1269.90145
Chan, T.-H. Hubert; Gupta, Anupam
2
2012
Online and stochastic survivable network design. Zbl 1260.05152
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
2
2012
Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 15th international workshop, APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge, MA, USA, August 15–17, 2012. Proceedings. Zbl 1248.68036
1
2012
Privately releasing conjunctions and the statistical query barrier. Zbl 1288.68141
Gupta, Anupam; Hardt, Moritz; Roth, Aaron; Ullman, Jonathan
104
2011
Approximation algorithms for correlated knapsacks and non-martingale bandits. Zbl 1292.90216
Gupta, Anupam; Krishnaswamy, Ravishankar; Molinaro, Marco; Ravi, Ramamoorthi
19
2011
Forest density estimation. Zbl 1280.62045
Liu, Han; Xu, Min; Gu, Haijie; Gupta, Anupam; Lafferty, John; Wasserman, Larry
13
2011
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1295.68211
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
11
2011
Welfare and profit maximization with production costs. Zbl 1292.91078
Blum, Avrim; Gupta, Anupam; Mansour, Yishay; Sharma, Ankit
6
2011
Sampling and cost-sharing: approximation algorithms for stochastic optimization problems. Zbl 1252.68352
Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha, Amitabh
5
2011
Simultaneous optimization of sensor placements and balanced schedules. Zbl 1368.90187
Krause, Andreas; Rajagopal, Ram; Gupta, Anupam; Guestrin, Carlos
1
2011
Scalably scheduling power-heterogeneous processors. Zbl 1288.68033
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
11
2010
A constant factor approximation algorithm for generalized MIN-sum set cover. Zbl 1288.68254
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar
11
2010
Approximation algorithms for optimal decision trees and adaptive TSP problems. Zbl 1288.68267
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
10
2010
When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract). Zbl 1287.05111
Bansal, Nikhil; Gupta, Anupam; Li, Jian; Mestre, Julián; Nagarajan, Viswanath; Rudra, Atri
7
2010
An improved approximation algorithm for requirement cut. Zbl 1194.05146
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
7
2010
Differentially private combinatorial optimization. Zbl 1288.94087
Gupta, Anupam; Ligett, Katrina; McSherry, Frank; Roth, Aaron; Talwar, Kunal
6
2010
Vertex sparsifiers: new results from old techniques. Zbl 1302.90233
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
5
2010
Dial a ride from \(k\)-forest. Zbl 1300.90010
Gupta, Anupam; Hajiaghayi, Mohammadtaghi; Nagarajan, Viswanath; Ravi, R.
4
2010
Thresholded covering algorithms for robust and max-min optimization. Zbl 1287.68180
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
4
2010
Ultra-low-dimensional embeddings for doubling metrics. Zbl 1327.46026
Chan, T.-H. Hubert; Gupta, Anupam; Talwar, Kunal
3
2010
Tree embeddings for two-edge-connected network design. Zbl 1288.68266
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
3
2010
A plant location guide for the unsure: approximation algorithms for min-Max location problems. Zbl 1219.90131
Anthony, Barbara; Goyal, Vineet; Gupta, Anupam; Nagarajan, Viswanath
2
2010
Scheduling with outliers. Zbl 1255.90060
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Segev, Danny
7
2009
Secretary problems: weights and discounts. Zbl 1422.68336
Babaioff, Moshe; Dinitz, Michael; Gupta, Anupam; Immorlica, Nicole; Talwar, Kunal
6
2009
Small hop-diameter sparse spanners for doubling metrics. Zbl 1163.68039
Chan, T.-H. Hubert; Gupta, Anupam
6
2009
Approximate clustering without the approximation. Zbl 1422.68287
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
5
2009
Metric embeddings with relaxed guarantees. Zbl 1191.68348
Chan, T.-H. Hubert; Dhamdhere, Kedar; Gupta, Anupam; Kleinberg, Jon; Slivkins, Aleksandrs
4
2009
Online and stochastic survivable network design. Zbl 1304.68139
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
4
2009
A constant-factor approximation for stochastic Steiner forest. Zbl 1304.68217
Gupta, Anupam; Kumar, Amit
3
2009
Stochastic analyses for online combinatorial optimization problems. Zbl 1192.90169
Garg, Naveen; Gupta, Anupam; Leonardi, Stefano; Sankowski, Piotr
14
2008
Cost-sharing mechanisms for network design. Zbl 1169.68314
Gupta, Anupam; Srinivasan, Aravind; Tardos, Éva
10
2008
Robust submodular observation selection. Zbl 1225.90107
Krause, Andreas; Mcmahan, H. Brendan; Guestrin, Carlos; Gupta, Anupam
10
2008
All-norms and all-\(L_p\)-norms approximation algorithms. Zbl 1248.68558
Golovin, Daniel; Gupta, Anupam; Kumar, Amit; Tangwongsan, Kanat
7
2008
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1192.68030
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
4
2008
Approximating TSP on metrics with bounded global growth. Zbl 1192.68874
Chan, T.-H. Hubert; Gupta, Anupam
2
2008
Ultra-low-dimensional embeddings for doubling metrics. Zbl 1192.68732
Chan, T.-H. Hubert; Gupta, Anupam; Talwar, Kunal
2
2008
On the approximability of some network design problems. Zbl 1445.68156
Chuzhoy, Julia; Gupta, Anupam; Naor, Joseph (Seffi); Sinha, Amitabh
2
2008
A plant location guide for the unsure. Zbl 1192.90098
Anthony, Barbara M.; Goyal, Vineet; Gupta, Anupam; Nagarajan, Viswanath
1
2008
Approximation algorithms for the unsplittable flow problem. Zbl 1107.68120
Chakrabarti, Amit; Chekuri, Chandra; Gupta, Anupam; Kumar, Amit
18
2007
Approximation via cost sharing: simpler and better approximation algorithms for network design. Zbl 1216.68339
Gupta, Anupam; Kumar, Amit; Pál, Martin; Roughgarden, Tim
16
2007
Infrastructure leasing problems. Zbl 1136.90447
Anthony, Barbara M.; Gupta, Anupam
10
2007
LP rounding approximation algorithms for stochastic network design. Zbl 1279.90030
Gupta, Anupam; Ravi, R.; Sinha, Amitabh
8
2007
An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem. Zbl 1302.90235
Gupta, A.; Könemann, J.; Leonardi, S.; Ravi, R.; Schäfer, G.
8
2007
Dial a ride from \(k\)-forest. Zbl 1151.68745
Gupta, Anupam; Hajiaghayi, MohammadTaghi; Nagarajan, Viswanath; Ravi, R.
5
2007
Stochastic Steiner tree with non-uniform inflation. Zbl 1171.90484
Gupta, Anupam; Hajiaghayi, MohammadTaghi; Kumar, Amit
5
2007
An \(O(\log ^{2} k)\)-competitive algorithm for metric bipartite matching. Zbl 1151.68742
Bansal, Nikhil; Buchbinder, Niv; Gupta, Anupam; Naor, Joseph (Seffi)
2
2007
...and 36 more Documents
all top 5

Cited by 1,391 Authors

18 Nagarajan, Viswanath
14 Gupta, Anupam
14 Neiman, Ofer
11 Dragan, Feodor F.
11 Naor, Assaf
9 Bansal, Nikhil
9 Chakrabarty, Deeparnab
9 Chekuri, Chandra S.
9 Kumar, Amit
9 Lee, James R.
8 Hajiaghayi, Mohammad Taghi
8 Im, Sungjin
8 Krishnaswamy, Ravishankar
8 Moseley, Benjamin
8 Rauch Henzinger, Monika
8 Ravi, Ramamoorthi
8 Talwar, Kunal
7 Angelopoulos, Spyros
7 Bartal, Yair
7 Elkin, Michael
7 Grandoni, Fabrizio
7 Mestre, Julián
7 Pruhs, Kirk R.
7 Roughgarden, Tim
7 Williamson, David P.
6 Khandekar, Rohit
6 Kortsarz, Guy
6 Leonardi, Stefano
6 Lokshtanov, Daniel
6 Ostrovskii, Mikhail Iosifovich
6 Salavatipour, Mohammad R.
6 Saurabh, Saket
6 Xu, Dachuan
5 Abraham, Ittai
5 Busch, Costas
5 Ene, Alina
5 Filtser, Arnold
5 Fomin, Fedor V.
5 Khot, Subhash Ajit
5 Krauthgamer, Robert
5 Levin, Asaf
5 Ljubić, Ivana
5 Lucarelli, Giorgio
5 Pilipczuk, Marcin L.
5 Sidiropoulos, Anastasios
5 Solomon, Shay
5 Srinivasan, Aravind
5 Swamy, Chaitanya
5 Wiese, Andreas
5 Xiang, Yang
4 Chalermsook, Parinya
4 Chan, T.-H. Hubert
4 Chepoi, Victor D.
4 Emek, Yuval
4 Feldman, Moran
4 Goranci, Gramoz
4 Huang, Zhiyi
4 Kane, Daniel M.
4 Khanna, Sanjeev
4 Leniowski, Dariusz
4 Meyer auf der Heide, Friedhelm
4 Naor, Joseph Seffi
4 Needell, Deanna
4 Nikolov, Aleksandar
4 Nutov, Zeev
4 Oriolo, Gianpaolo
4 Rothvoß, Thomas
4 Sabharwal, Yogish
4 Schafer, Guido
4 Schmid, Stefan
4 Schmidt, Daniel R.
4 Scutellà, Maria Grazia
4 Segev, Danny
4 Shmoys, David B.
4 Sitters, Rene A.
4 Skutella, Martin
4 Sviridenko, Maxim I.
4 Ullman, Jonathan R.
4 Umboh, Seeun William
4 van Zuylen, Anke
4 Verschae, José
4 Vondrák, Jan
4 Wattenhofer, Roger P.
4 Zenklusen, Rico
4 Zhang, Dongmei
3 Adamczyk, Marek
3 Albers, Susanne
3 Antoniadis, Antonios Foivos
3 Bampis, Evripidis
3 Bernstein, Aaron
3 Bhattacharya, Sayan
3 Blado, Daniel
3 Blum, Avrim L.
3 Bun, Mark
3 Chakaravarthy, Venkatesan T.
3 Charikar, Moses S.
3 Chen, Ning
3 Choudhury, Anamitra Roy
3 Christodoulou, George C.
3 Chuzhoy, Julia
...and 1,291 more Authors
all top 5

Cited in 136 Serials

69 Algorithmica
60 Theoretical Computer Science
45 SIAM Journal on Computing
22 Discrete Applied Mathematics
22 Mathematical Programming. Series A. Series B
22 Journal of Combinatorial Optimization
20 Operations Research Letters
19 Information Processing Letters
17 Mathematics of Operations Research
16 Discrete & Computational Geometry
15 Journal of Computer and System Sciences
15 SIAM Journal on Discrete Mathematics
13 European Journal of Operational Research
13 Theory of Computing Systems
11 Journal of Machine Learning Research (JMLR)
10 Operations Research
8 Discrete Optimization
7 Journal of Scheduling
6 Networks
6 Distributed Computing
5 The Annals of Statistics
5 Games and Economic Behavior
5 INFORMS Journal on Computing
5 Optimization Letters
4 Computers & Operations Research
4 Computational Optimization and Applications
4 Journal of Discrete Algorithms
3 Artificial Intelligence
3 Random Structures & Algorithms
3 Computational Geometry
3 Applied and Computational Harmonic Analysis
3 Algorithms
3 Information and Inference
3 Journal of the Operations Research Society of China
2 Communications in Mathematical Physics
2 Information Sciences
2 Journal of the American Statistical Association
2 Journal of Computational and Applied Mathematics
2 Journal of Functional Analysis
2 Combinatorica
2 Information and Computation
2 Machine Learning
2 Journal of Global Optimization
2 Linear Algebra and its Applications
2 Computational Statistics and Data Analysis
2 SIAM Journal on Optimization
2 Optimization Methods & Software
2 Positivity
2 Journal of the ACM
2 International Journal of Applied Mathematics and Computer Science
2 RAIRO. Operations Research
2 Foundations of Computational Mathematics
2 Mathematical Programming Computation
2 Stochastic Systems
2 Analysis and Geometry in Metric Spaces
1 ACM Computing Surveys
1 Discrete Mathematics
1 Israel Journal of Mathematics
1 Journal of Mathematical Analysis and Applications
1 Journal of Mathematical Physics
1 Journal of Statistical Physics
1 Linear and Multilinear Algebra
1 Mathematical Methods in the Applied Sciences
1 Acta Mathematica
1 Advances in Mathematics
1 Applied Mathematics and Computation
1 Applied Mathematics and Optimization
1 Automatica
1 BIT
1 Canadian Journal of Mathematics
1 Geometriae Dedicata
1 Inventiones Mathematicae
1 Journal of Combinatorial Theory. Series B
1 Journal of Graph Theory
1 Journal of the London Mathematical Society. Second Series
1 Journal of Multivariate Analysis
1 Mathematische Annalen
1 Mathematika
1 Proceedings of the American Mathematical Society
1 Results in Mathematics
1 Transactions of the American Mathematical Society
1 European Journal of Combinatorics
1 Systems & Control Letters
1 Journal of Classification
1 Acta Mathematicae Applicatae Sinica. English Series
1 Statistical Science
1 Asia-Pacific Journal of Operational Research
1 Journal of Theoretical Probability
1 Journal of the American Mathematical Society
1 SIAM Journal on Matrix Analysis and Applications
1 Signal Processing
1 Annals of Operations Research
1 Neural Computation
1 The Annals of Applied Probability
1 Numerical Algorithms
1 Geometric and Functional Analysis. GAFA
1 Automation and Remote Control
1 SIAM Journal on Mathematical Analysis
1 Journal of Mathematical Imaging and Vision
1 Computational Complexity
...and 36 more Serials
all top 5

Cited in 36 Fields

508 Computer science (68-XX)
328 Operations research, mathematical programming (90-XX)
206 Combinatorics (05-XX)
62 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
55 Information and communication theory, circuits (94-XX)
41 Statistics (62-XX)
33 Functional analysis (46-XX)
31 Numerical analysis (65-XX)
24 Probability theory and stochastic processes (60-XX)
16 Linear and multilinear algebra; matrix theory (15-XX)
9 Functions of a complex variable (30-XX)
8 General topology (54-XX)
8 Quantum theory (81-XX)
8 Systems theory; control (93-XX)
7 Biology and other natural sciences (92-XX)
6 Harmonic analysis on Euclidean spaces (42-XX)
6 Geometry (51-XX)
5 Convex and discrete geometry (52-XX)
4 Group theory and generalizations (20-XX)
3 Measure and integration (28-XX)
3 Calculus of variations and optimal control; optimization (49-XX)
3 Differential geometry (53-XX)
3 Statistical mechanics, structure of matter (82-XX)
2 General and overarching topics; collections (00-XX)
2 Number theory (11-XX)
2 Operator theory (47-XX)
2 Manifolds and cell complexes (57-XX)
1 Mathematical logic and foundations (03-XX)
1 Algebraic geometry (14-XX)
1 Topological groups, Lie groups (22-XX)
1 Dynamical systems and ergodic theory (37-XX)
1 Approximations and expansions (41-XX)
1 Abstract harmonic analysis (43-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Mechanics of deformable solids (74-XX)
1 Optics, electromagnetic theory (78-XX)

Citations by Year