×
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
all top 5

Co-Authors

6 single-authored
34 Kumar, Amit
30 Nagarajan, Viswanath
27 Ravi, Ramamoorthi
16 Krishnaswamy, Ravishankar
14 Talwar, Kunal
11 Bansal, Nikhil
10 Li, Jason
9 Chan, T.-H. Hubert
9 Chekuri, Chandra S.
8 Guruganesh, Guru Prashanth
8 Lee, Euiwoong
8 Racke, Harald
8 Singla, Sahil
7 Naor, Joseph Seffi
6 Dhamdhere, Kedar
6 Leonardi, Stefano
6 Molinaro, Marco
5 Abraham, Ittai
5 Argue, C. J.
5 Neiman, Ofer
5 Pál, Martin
5 Pruhs, Kirk R.
5 Rabinovich, Yuri
5 Sinha, Amitabh
4 Hajiaghayi, Mohammad Taghi
4 Maggs, Bruce M.
4 Panigrahi, Debmalya
4 Roth, Aaron Leon
4 Shen, Xiangkun
4 Srinivasan, Aravind
3 Anthony, Barbara M.
3 Blum, Avrim L.
3 Buchbinder, Niv
3 Dinitz, Michael H.
3 Englert, Matthias
3 Filtser, Arnold
3 Goyal, Vineet
3 Krauthgamer, Robert
3 Newman, Ilan I.
3 Sankowski, Piotr
3 Segev, Danny
3 Sidiropoulos, Anastasios
3 Sinclair, Alistair
3 Singh, Mohit
3 Stein, Clifford
3 Tang, Ziye
3 Tardos, Éva
3 Ullman, Jonathan R.
2 Andoni, Alexandr
2 Babenko, Maxim A.
2 Bădoiu, Mihai
2 Balcan, Maria-Florina
2 Chakrabarti, Amit
2 Chawla, Shuchi
2 Chuzhoy, Julia
2 Cohen-Addad, Vincent
2 Even, Guy
2 Friggstad, Zachary
2 Garg, Naveen Kumar
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 Li, Jian
2 Mestre, Julián
2 Moseley, Benjamin
2 Mucha, Marcin
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 Talgam-Cohen, Inbal
2 Tangwongsan, Kanat
2 Wajc, David
2 Zhou, Shuheng
1 Arora, Nipun
1 Babaioff, Moshe
1 Bahga, Supreet S.
1 Blelloch, Guy E.
1 Bradač, Domagoj
1 Bubeck, Sébastien
1 Chan, Hubert T-H.
1 Cohen, Michael B.
1 Cygan, Marek
1 Dasgupta, Sanjoy
1 Deza, Michel Marie
1 Eberle, Franziska
1 Feldkord, Björn
1 Feldotto, Matthias
1 Ghuge, Rohan
...and 59 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

157 Publications have been cited 1,679 times in 1,162 Documents Cited by Year
An elementary proof of a theorem of Johnson and Lindenstrauss. Zbl 1018.51010
Dasgupta, Sanjoy; Gupta, Anupam
116
2003
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
100
2012
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
56
2001
Cuts, trees and \(\ell_1\)-embeddings of graphs. Zbl 1056.05040
Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair
39
2004
Approximation algorithms for correlated knapsacks and non-martingale bandits. Zbl 1292.90216
Gupta, Anupam; Krishnaswamy, Ravishankar; Molinaro, Marco; Ravi, Ramamoorthi
31
2011
Simpler and better approximation algorithms for network design. Zbl 1192.90226
Gupta, Anupam; Kumar, Amit; Roughgarden, Tim
30
2003
Steiner points in tree metrics don’t (really) help. Zbl 0990.05033
Gupta, Anupam
29
2001
Robust submodular observation selection. Zbl 1225.90107
Krause, Andreas; Mcmahan, H. Brendan; Guestrin, Carlos; Gupta, Anupam
27
2008
Changing bases: multistage optimization for matroids and matchings. Zbl 1423.90067
Gupta, Anupam; Talwar, Kunal; Wieder, Udi
25
2014
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
25
2005
A stochastic probing problem with applications. Zbl 1372.90091
Gupta, Anupam; Nagarajan, Viswanath
23
2013
Approximation algorithms for the unsplittable flow problem. Zbl 1107.68120
Chakrabarti, Amit; Chekuri, Chandra; Gupta, Anupam; Kumar, Amit
22
2007
On hierarchical routing in doubling metrics. Zbl 1297.68090
Chan, Hubert T-H.; Gupta, Anupam; Maggs, Bruce M.; Zhou, Shuheng
22
2005
Boosted sampling: approximation algorithms for stochastic optimization. Zbl 1192.90171
Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha Amitabh
21
2004
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
20
2012
Approximation via cost sharing: simpler and better approximation algorithms for network design. Zbl 1216.68339
Gupta, Anupam; Kumar, Amit; Pál, Martin; Roughgarden, Tim
19
2007
Traveling with a pez dispenser (or, routing issues in MPLS). Zbl 1087.68013
Gupta, Anupam; Kumar, Amit; Rastogi, Rajeev
19
2005
Stochastic analyses for online combinatorial optimization problems. Zbl 1192.90169
Garg, Naveen; Gupta, Anupam; Leonardi, Stefano; Sankowski, Piotr
19
2008
Oblivious network design. Zbl 1192.68037
Gupta, Anupam; Hajiaghayi, Mohammad T.; Räcke, Harald
18
2006
An FPT algorithm beating 2-approximation for \(k\)-cut. Zbl 1403.68350
Gupta, Anupam; Lee, Euiwoong; Li, Jason
17
2018
The online metric matching problem for doubling metrics. Zbl 1272.90068
Gupta, Anupam; Lewi, Kevin
17
2012
Online and dynamic algorithms for set cover. Zbl 1370.90217
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Panigrahi, Debmalya
16
2017
Forest density estimation. Zbl 1280.62045
Liu, Han; Xu, Min; Gu, Haijie; Gupta, Anupam; Lafferty, John; Wasserman, Larry
16
2011
Differentially private combinatorial optimization. Zbl 1288.94087
Gupta, Anupam; Ligett, Katrina; McSherry, Frank; Roth, Aaron; Talwar, Kunal
16
2010
Infrastructure leasing problems. Zbl 1136.90447
Anthony, Barbara M.; Gupta, Anupam
15
2007
Approximation algorithms for VRP with stochastic demands. Zbl 1247.90050
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
15
2012
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1295.68211
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
15
2011
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
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1333.68301
Gu, Albert; Gupta, Anupam; Kumar, Amit
15
2016
Online primal-dual for non-linear optimization with applications to speed scaling. Zbl 1394.68447
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
15
2013
Embedding \(k\)-outerplanar graphs into \(\ell_1\). Zbl 1111.05022
Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair
14
2006
Scalably scheduling power-heterogeneous processors. Zbl 1288.68033
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
14
2010
All-norms and all-\(L_p\)-norms approximation algorithms. Zbl 1248.68558
Golovin, Daniel; Gupta, Anupam; Kumar, Amit; Tangwongsan, Kanat
13
2008
Sparsest cut on bounded treewidth graphs: algorithms and hardness results. Zbl 1293.05042
Gupta, Anupam; Talwar, Kunal; Witmer, David
13
2013
Vertex sparsifiers: new results from old techniques. Zbl 1302.90234
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
13
2014
A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching. Zbl 1318.68200
Bansal, Nikhil; Buchbinder, Niv; Gupta, Anupam; Naor, Joseph (seffi)
13
2014
Fully-dynamic bin packing with little repacking. Zbl 1499.68411
Feldkord, Björn; Feldotto, Matthias; Gupta, Anupam; Guruganesh, Guru; Kumar, Amit; Riechers, Sören; Wajc, David
13
2018
Packing interdiction and partial covering problems. Zbl 1372.90110
Dinitz, Michael; Gupta, Anupam
13
2013
Adaptivity gaps for stochastic probing: submodular and XOS functions. Zbl 1423.90159
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
13
2017
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. Zbl 1315.05130
Abraham, Ittai; Gavoille, Cyril; Gupta, Anupam; Neiman, Ofer; Talwar, Kunal
12
2014
Losing treewidth by separating subsets. Zbl 1432.68355
Gupta, Anupam; Lee, Euiwoong; Li, Jason; Manurangsi, Pasin; Włodarczyk, Michał
12
2019
Maintaining assignments online: matching, scheduling, and flows. Zbl 1421.68250
Gupta, Anupam; Kumar, Amit; Stein, Cliff
12
2014
Improved results for directed multicut. Zbl 1092.68627
Gupta, Anupam
11
2003
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.
11
2007
A constant factor approximation algorithm for generalized MIN-sum set cover. Zbl 1288.68254
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar
11
2010
Approximating unique games. Zbl 1192.91012
Gupta, Anupam; Talwar, Kunal
11
2006
Algorithms and adaptivity gaps for stochastic probing. Zbl 1415.90102
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
11
2016
Spanners with slack. Zbl 1131.68482
Chan, T.-H. Hubert; Dinitz, Michael; Gupta, Anupam
10
2006
LP rounding approximation algorithms for stochastic network design. Zbl 1279.90030
Gupta, Anupam; Ravi, R.; Sinha, Amitabh
10
2007
Improved bandwidth approximation for trees and chordal graphs. Zbl 0979.68066
Gupta, Anupam
10
2001
Running errands in time: approximation algorithms for stochastic orienteering. Zbl 1328.90067
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
10
2015
Approximation algorithms for optimal decision trees and adaptive TSP problems. Zbl 1288.68267
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
10
2010
Tight FPT approximations for \(k\)-median and \(k\)-means. Zbl 07561535
Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason
10
2019
On hierarchical routing in doubling metrics. Zbl 1445.68108
Chan, T.-H. Hubert; Gupta, Anupam; Maggs, Bruce M.; Zhou, Shuheng
10
2016
Online Steiner tree with deletions. Zbl 1421.68249
Gupta, Anupam; Kumar, Amit
10
2014
Cost-sharing mechanisms for network design. Zbl 1169.68314
Gupta, Anupam; Srinivasan, Aravind; Tardos, Éva
9
2008
Sampling and cost-sharing: approximation algorithms for stochastic optimization problems. Zbl 1252.68352
Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha, Amitabh
9
2011
Cost-sharing mechanisms for network design. Zbl 1105.68304
Gupta, Anupam; Srinivasan, Aravind; Tardos, Éva
9
2004
Scheduling with outliers. Zbl 1255.90060
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Segev, Danny
9
2009
Greedy algorithms for Steiner forest. Zbl 1321.68504
Gupta, Anupam; Kumar, Amit
9
2015
Potential-function proofs for gradient methods. Zbl 1482.90145
Bansal, Nikhil; Gupta, Anupam
9
2019
Secretary problems: weights and discounts. Zbl 1422.68336
Babaioff, Moshe; Dinitz, Michael; Gupta, Anupam; Immorlica, Nicole; Talwar, Kunal
9
2009
Scheduling heterogeneous processors isn’t as easy as you think. Zbl 1421.68248
Gupta, Anupam; Im, Sungjin; Krishnaswamy, Ravishankar; Moseley, Benjamin; Pruhs, Kirk
9
2012
Clustering under approximation stability. Zbl 1281.68232
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
9
2013
Robust and max-min optimization under matroid and knapsack uncertainty sets. Zbl 1398.68689
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
9
2016
Small hop-diameter sparse spanners for doubling metrics. Zbl 1163.68039
Chan, T.-H. Hubert; Gupta, Anupam
8
2009
Welfare and profit maximization with production costs. Zbl 1292.91078
Blum, Avrim; Gupta, Anupam; Mansour, Yishay; Sharma, Ankit
8
2011
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1293.05041
Gu, Albert; Gupta, Anupam; Kumar, Amit
8
2013
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
8
2014
Approximate clustering without the approximation. Zbl 1422.68287
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
8
2009
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
8
2010
An improved approximation algorithm for requirement cut. Zbl 1194.05146
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
8
2010
On the approximability of some network design problems. Zbl 1445.68156
Chuzhoy, Julia; Gupta, Anupam; Naor, Joseph (Seffi); Sinha, Amitabh
8
2008
Stochastic Steiner trees without a root. Zbl 1084.90034
Gupta, Anupam; Pál, Martin
7
2005
What about Wednesday? Approximation algorithms for multistage stochastic optimization. Zbl 1142.90461
Gupta, Anupam; Pál, Martin; Ravi, Ramamoorthi; Sinha, Amitabh
7
2005
Thresholded covering algorithms for robust and max-min optimization. Zbl 1297.05188
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
7
2014
On the approximability of some network design problems. Zbl 1297.68019
Chuzhoy, Julia; Gupta, Anupam; Naor, Joseph (Seffi); Sinha, Amitabh
7
2005
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
7
2015
On the Lovász theta function for independent sets in sparse graphs. Zbl 1321.05176
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru
7
2015
Approximation algorithms for stochastic orienteering. Zbl 1423.90106
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
7
2012
Tree embeddings for two-edge-connected network design. Zbl 1288.68266
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
7
2010
Set covering with our eyes closed. Zbl 1275.68158
Grandoni, Fabrizio; Gupta, Anupam; Leonardi, Stefano; Miettinen, Pauli; Sankowski, Piotr; Singh, Mohit
7
2013
Towards \((1 + \varepsilon)\)-approximate flow sparsifiers. Zbl 1422.68280
Andoni, Alexandr; Gupta, Anupam; Krauthgamer, Robert
7
2014
Embedding tree metrics into low-dimensional Euclidean spaces. Zbl 0977.68086
Gupta, Anupam
6
2000
Stochastic Steiner tree with non-uniform inflation. Zbl 1171.90484
Gupta, Anupam; Hajiaghayi, MohammadTaghi; Kumar, Amit
6
2007
Dial a ride from \(k\)-forest. Zbl 1300.90010
Gupta, Anupam; Hajiaghayi, Mohammadtaghi; Nagarajan, Viswanath; Ravi, R.
6
2010
An \(O(\log ^{2} k)\)-competitive algorithm for metric bipartite matching. Zbl 1151.68742
Bansal, Nikhil; Buchbinder, Niv; Gupta, Anupam; Naor, Joseph (Seffi)
6
2007
Metric embeddings with relaxed guarantees. Zbl 1191.68348
Chan, T.-H. Hubert; Dhamdhere, Kedar; Gupta, Anupam; Kleinberg, Jon; Slivkins, Aleksandrs
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
Embedding \(k\)-outerplanar graphs into \(\ell_1\). Zbl 1092.68619
Chekuri, Chandra; Gupta, Anupam; Newman, Ilan; Rabinovich, Yuri; Sinclair, Alistair
5
2003
How experts can solve LPs online. Zbl 1425.90066
Gupta, Anupam; Molinaro, Marco
5
2014
Approximating sparse covering integer programs online. Zbl 1327.68338
Gupta, Anupam; Nagarajan, Viswanath
5
2014
Approximation algorithms for the unsplittable flow problem. Zbl 1013.90112
Chakrabarti, Amit; Chekuri, Chandra; Gupta, Anupam; Kumar, Amit
5
2002
Dial a ride from \(k\)-forest. Zbl 1151.68745
Gupta, Anupam; Hajiaghayi, MohammadTaghi; Nagarajan, Viswanath; Ravi, R.
5
2007
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1192.68030
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
5
2008
Chasing convex bodies with linear competitive ratio. Zbl 07304116
Argue, C. J.; Gupta, Anupam; Guruganesh, Guru; Tang, Ziye
5
2020
Small hop-diameter sparse spanners for doubling metrics. Zbl 1192.05037
Chan, T.-H. Hubert; Gupta, Anupam
5
2006
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
Thresholded covering algorithms for robust and max-min optimization. Zbl 1287.68180
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
5
2010
Non-adaptive stochastic score classification and explainable halfspace evaluation. Zbl 1497.90138
Ghuge, Rohan; Gupta, Anupam; Nagarajan, Viswanath
2
2022
Matroid-based TSP rounding for half-integral solutions. Zbl 1497.90173
Gupta, Anupam; Lee, Euiwoong; Li, Jason; Mucha, Marcin; Newman, Heather; Sarkar, Sherry
2
2022
Metric embedding via shortest path decompositions. Zbl 07510286
Abraham, Ittai; Filtser, Arnold; Gupta, Anupam; Neiman, Ofer
1
2022
Stochastic makespan minimization in structured set systems. Zbl 07495433
Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
1
2022
Stochastic load balancing on unrelated machines. Zbl 1516.90026
Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
2
2021
Random-order models. Zbl 07469258
Gupta, Anupam; Singla, Sahil
2
2021
A quasipolynomial \((2+\varepsilon)\)-approximation for planar sparsest cut. Zbl 07765231
Cohen-Addad, Vincent; Gupta, Anupam; Klein, Philip N.; Li, Jason
1
2021
Chasing convex bodies with linear competitive ratio. Zbl 07304116
Argue, C. J.; Gupta, Anupam; Guruganesh, Guru; Tang, Ziye
5
2020
The Karger-Stein algorithm is optimal for k-cut. Zbl 07298263
Gupta, Anupam; Lee, Euiwoong; Li, Jason
4
2020
Robust algorithms for the secretary problem. Zbl 07650380
Bradac, Domagoj; Gupta, Anupam; Singla, Sahil; Zuzic, Goran
1
2020
Losing treewidth by separating subsets. Zbl 1432.68355
Gupta, Anupam; Lee, Euiwoong; Li, Jason; Manurangsi, Pasin; Włodarczyk, Michał
12
2019
Tight FPT approximations for \(k\)-median and \(k\)-means. Zbl 07561535
Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason
10
2019
Potential-function proofs for gradient methods. Zbl 1482.90145
Bansal, Nikhil; Gupta, Anupam
9
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
5
2019
Stochastic online metric matching. Zbl 1523.68174
Gupta, Anupam; Guruganesh, Guru; Peng, Binghui; Wajc, David
4
2019
The number of minimum \(k\)-cuts: improving the Karger-Stein bound. Zbl 1437.05222
Gupta, Anupam; Lee, Euiwoong; Li, Jason
4
2019
\(k\)-servers with a smile: online algorithms via projections. Zbl 1431.68160
Buchbinder, Niv; Gupta, Anupam; Molinaro, Marco; Naor, Joseph (Seffi)
3
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
3
2019
The Markovian price of information. Zbl 1436.90149
Gupta, Anupam; Jiang, Haotian; Scully, Ziv; Singla, Sahil
3
2019
Non-clairvoyant precedence constrained scheduling. Zbl 07561556
Garg, Naveen; Gupta, Anupam; Kumar, Amit; Singla, Sahil
1
2019
An FPT algorithm beating 2-approximation for \(k\)-cut. Zbl 1403.68350
Gupta, Anupam; Lee, Euiwoong; Li, Jason
17
2018
Fully-dynamic bin packing with little repacking. Zbl 1499.68411
Feldkord, Björn; Feldotto, Matthias; Gupta, Anupam; Guruganesh, Guru; Kumar, Amit; Riechers, Sören; Wajc, David
13
2018
A local-search algorithm for Steiner forest. Zbl 1462.68140
Groß, Martin; Gupta, Anupam; Kumar, Amit; Matuschke, Jannik; Schmidt, Daniel R.; Schmidt, Melanie; Verschae, José
5
2018
On the Lovász theta function for independent sets in sparse graphs. Zbl 1397.05124
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru
5
2018
Metric embedding via shortest path decompositions. Zbl 1427.68322
Abraham, Ittai; Filtser, Arnold; Gupta, Anupam; Neiman, Ofer
3
2018
Stochastic load balancing on unrelated machines. Zbl 1403.90385
Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
2
2018
Maximizing profit with convex costs in the random-order model. Zbl 1499.68413
Gupta, Anupam; Mehta, Ruta; Molinaro, Marco
2
2018
Analysis of passive flexion in propelling a plunging plate using a torsion spring model. Zbl 1415.76786
Arora, N.; Kang, C.-K.; Shyy, W.; Gupta, A.
1
2018
Online and dynamic algorithms for set cover. Zbl 1370.90217
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Panigrahi, Debmalya
16
2017
Adaptivity gaps for stochastic probing: submodular and XOS functions. Zbl 1423.90159
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
13
2017
LAST but not least: online spanners for buy-at-bulk. Zbl 1410.68298
Gupta, Anupam; Ravi, R.; Talwar, Kunal; Umboh, Seeun William
4
2017
Approximation algorithms for optimal decision trees and adaptive TSP problems. Zbl 1420.68236
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
2
2017
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1333.68301
Gu, Albert; Gupta, Anupam; Kumar, Amit
15
2016
Algorithms and adaptivity gaps for stochastic probing. Zbl 1415.90102
Gupta, Anupam; Nagarajan, Viswanath; Singla, Sahil
11
2016
On hierarchical routing in doubling metrics. Zbl 1445.68108
Chan, T.-H. Hubert; Gupta, Anupam; Maggs, Bruce M.; Zhou, Shuheng
10
2016
Robust and max-min optimization under matroid and knapsack uncertainty sets. Zbl 1398.68689
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
9
2016
How the experts algorithm can help solve LPs online. Zbl 1349.90604
Gupta, Anupam; Molinaro, Marco
4
2016
An improved integrality gap for asymmetric TSP paths. Zbl 1371.90120
Friggstad, Zachary; Gupta, Anupam; Singh, Mohit
3
2016
Approximation algorithms for aversion \(k\)-clustering via local \(k\)-median. Zbl 1388.68308
Gupta, Anupam; Guruganesh, Guru; Schmidt, Melanie
2
2016
Running errands in time: approximation algorithms for stochastic orienteering. Zbl 1328.90067
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
10
2015
Greedy algorithms for Steiner forest. Zbl 1321.68504
Gupta, Anupam; Kumar, Amit
9
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
7
2015
On the Lovász theta function for independent sets in sparse graphs. Zbl 1321.05176
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru
7
2015
Efficient cost-sharing mechanisms for prize-collecting problems. Zbl 1319.90056
Gupta, A.; Könemann, Jochen; Leonardi, S.; Ravi, R.; Schäfer, G.
2
2015
Changing bases: multistage optimization for matroids and matchings. Zbl 1423.90067
Gupta, Anupam; Talwar, Kunal; Wieder, Udi
25
2014
Vertex sparsifiers: new results from old techniques. Zbl 1302.90234
Englert, Matthias; Gupta, Anupam; Krauthgamer, Robert; Räcke, Harald; Talgam-Cohen, Inbal; Talwar, Kunal
13
2014
A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching. Zbl 1318.68200
Bansal, Nikhil; Buchbinder, Niv; Gupta, Anupam; Naor, Joseph (seffi)
13
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
12
2014
Maintaining assignments online: matching, scheduling, and flows. Zbl 1421.68250
Gupta, Anupam; Kumar, Amit; Stein, Cliff
12
2014
Online Steiner tree with deletions. Zbl 1421.68249
Gupta, Anupam; Kumar, Amit
10
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
8
2014
Thresholded covering algorithms for robust and max-min optimization. Zbl 1297.05188
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
7
2014
Towards \((1 + \varepsilon)\)-approximate flow sparsifiers. Zbl 1422.68280
Andoni, Alexandr; Gupta, Anupam; Krauthgamer, Robert
7
2014
How experts can solve LPs online. Zbl 1425.90066
Gupta, Anupam; Molinaro, Marco
5
2014
Approximating sparse covering integer programs online. Zbl 1327.68338
Gupta, Anupam; Nagarajan, Viswanath
5
2014
A stochastic probing problem with applications. Zbl 1372.90091
Gupta, Anupam; Nagarajan, Viswanath
23
2013
Online primal-dual for non-linear optimization with applications to speed scaling. Zbl 1394.68447
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
15
2013
Sparsest cut on bounded treewidth graphs: algorithms and hardness results. Zbl 1293.05042
Gupta, Anupam; Talwar, Kunal; Witmer, David
13
2013
Packing interdiction and partial covering problems. Zbl 1372.90110
Dinitz, Michael; Gupta, Anupam
13
2013
Clustering under approximation stability. Zbl 1281.68232
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
9
2013
The power of deferral: maintaining a constant-competitive Steiner tree online. Zbl 1293.05041
Gu, Albert; Gupta, Anupam; Kumar, Amit
8
2013
Set covering with our eyes closed. Zbl 1275.68158
Grandoni, Fabrizio; Gupta, Anupam; Leonardi, Stefano; Miettinen, Pauli; Sankowski, Piotr; Singh, Mohit
7
2013
The approximability of the binary paintshop problem. Zbl 1407.68194
Gupta, Anupam; Kale, Satyen; Nagarajan, Viswanath; Saket, Rishi; Schieber, Baruch
3
2013
Privately releasing conjunctions and the statistical query barrier. Zbl 1290.68062
Gupta, Anupam; Hardt, Moritz; Roth, Aaron; Ullman, Jonathan
3
2013
Algorithms for hub label optimization. Zbl 1336.68287
Babenko, Maxim; Goldberg, Andrew V.; Gupta, Anupam; Nagarajan, Viswanath
2
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
100
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
20
2012
The online metric matching problem for doubling metrics. Zbl 1272.90068
Gupta, Anupam; Lewi, Kevin
17
2012
Approximation algorithms for VRP with stochastic demands. Zbl 1247.90050
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
15
2012
Scheduling heterogeneous processors isn’t as easy as you think. Zbl 1421.68248
Gupta, Anupam; Im, Sungjin; Krishnaswamy, Ravishankar; Moseley, Benjamin; Pruhs, Kirk
9
2012
Approximation algorithms for stochastic orienteering. Zbl 1423.90106
Gupta, Anupam; Krishnaswamy, Ravishankar; Nagarajan, Viswanath; Ravi, R.
7
2012
Online and stochastic survivable network design. Zbl 1260.05152
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
5
2012
Approximating TSP on metrics with bounded global growth. Zbl 1269.90145
Chan, T.-H. Hubert; Gupta, Anupam
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
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
31
2011
Forest density estimation. Zbl 1280.62045
Liu, Han; Xu, Min; Gu, Haijie; Gupta, Anupam; Lafferty, John; Wasserman, Larry
16
2011
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1295.68211
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
15
2011
Sampling and cost-sharing: approximation algorithms for stochastic optimization problems. Zbl 1252.68352
Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha, Amitabh
9
2011
Welfare and profit maximization with production costs. Zbl 1292.91078
Blum, Avrim; Gupta, Anupam; Mansour, Yishay; Sharma, Ankit
8
2011
Making doubling metrics geodesic. Zbl 1213.68454
Gupta, Anupam; Talwar, Kunal
2
2011
Simultaneous optimization of sensor placements and balanced schedules. Zbl 1368.90187
Krause, Andreas; Rajagopal, Ram; Gupta, Anupam; Guestrin, Carlos
1
2011
Differentially private combinatorial optimization. Zbl 1288.94087
Gupta, Anupam; Ligett, Katrina; McSherry, Frank; Roth, Aaron; Talwar, Kunal
16
2010
Scalably scheduling power-heterogeneous processors. Zbl 1288.68033
Gupta, Anupam; Krishnaswamy, Ravishankar; Pruhs, Kirk
14
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
8
2010
An improved approximation algorithm for requirement cut. Zbl 1194.05146
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
8
2010
Tree embeddings for two-edge-connected network design. Zbl 1288.68266
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R.
7
2010
Dial a ride from \(k\)-forest. Zbl 1300.90010
Gupta, Anupam; Hajiaghayi, Mohammadtaghi; Nagarajan, Viswanath; Ravi, R.
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
Thresholded covering algorithms for robust and max-min optimization. Zbl 1287.68180
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
5
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
4
2010
Ultra-low-dimensional embeddings for doubling metrics. Zbl 1327.46026
Chan, T.-H. Hubert; Gupta, Anupam; Talwar, Kunal
3
2010
Scheduling with outliers. Zbl 1255.90060
Gupta, Anupam; Krishnaswamy, Ravishankar; Kumar, Amit; Segev, Danny
9
2009
Secretary problems: weights and discounts. Zbl 1422.68336
Babaioff, Moshe; Dinitz, Michael; Gupta, Anupam; Immorlica, Nicole; Talwar, Kunal
9
2009
Small hop-diameter sparse spanners for doubling metrics. Zbl 1163.68039
Chan, T.-H. Hubert; Gupta, Anupam
8
2009
Approximate clustering without the approximation. Zbl 1422.68287
Balcan, Maria-Florina; Blum, Avrim; Gupta, Anupam
8
2009
...and 57 more Documents
all top 5

Cited by 1,924 Authors

24 Gupta, Anupam
22 Nagarajan, Viswanath
22 Neiman, Ofer
14 Kumar, Amit
13 Dragan, Feodor F.
13 Ravi, Ramamoorthi
12 Sidiropoulos, Anastasios
12 Williamson, David P.
11 Moseley, Benjamin
11 Naor, Assaf
10 Bampis, Evripidis
10 Chekuri, Chandra S.
10 Elkin, Michael
10 Escoffier, Bruno
10 Filtser, Arnold
10 Grandoni, Fabrizio
10 Lee, James R.
10 Rauch Henzinger, Monika
10 Saurabh, Saket
9 Bansal, Nikhil
9 Bartal, Yair
9 Chakrabarty, Deeparnab
9 Fomin, Fedor V.
9 Hajiaghayi, Mohammad Taghi
9 Im, Sungjin
9 Krishnaswamy, Ravishankar
9 Levin, Asaf
9 Lokshtanov, Daniel
9 Naor, Joseph Seffi
9 Pruhs, Kirk R.
8 Talwar, Kunal
7 Abraham, Ittai
7 Angelopoulos, Spyros
7 Busch, Costas
7 Leonardi, Stefano
7 Ostrovskii, Mikhail Iosifovich
7 Panigrahi, Debmalya
7 Roughgarden, Tim
7 Salavatipour, Mohammad R.
7 Solomon, Shay
7 Swamy, Chaitanya
6 Albers, Susanne
6 Du, Donglei
6 Friggstad, Zachary
6 Khandekar, Rohit
6 Khot, Subhash Ajit
6 Kortsarz, Guy
6 Krauthgamer, Robert
6 Ljubić, Ivana
6 Manurangsi, Pasin
6 Meyer auf der Heide, Friedhelm
6 Niedermeier, Rolf
6 Nutov, Zeev
6 Schafer, Guido
6 Shepherd, F. Bruce
6 Shmoys, David B.
6 Umboh, Seeun William
6 Wiese, Andreas
6 Xiang, Yang
6 Xu, Dachuan
6 Zenklusen, Rico
6 Zhang, Zhen
5 Antoniadis, Antonios Foivos
5 Berndt, Sebastian
5 Chalermsook, Parinya
5 Disser, Yann
5 Emek, Yuval
5 Ene, Alina
5 Feldman, Moran
5 Feng, Qilong
5 Golovach, Petr A.
5 Goranci, Gramoz
5 Heggernes, Pinar
5 Jansen, Klaus
5 Kobourov, Stephen G.
5 Leniowski, Dariusz
5 Li, Jian
5 Li, Weidong
5 Lucarelli, Giorgio
5 Makarychev, Yury S.
5 Megow, Nicole
5 Meister, Daniel
5 Pilipczuk, Marcin L.
5 Sabharwal, Yogish
5 Sahneh, Faryad Darabi
5 Schmid, Stefan
5 Segev, Danny
5 Sharma, Gokarna
5 Shen, Xiangkun
5 Sitters, Rene A.
5 Skutella, Martin
5 Spence, Richard
5 Srinivasan, Aravind
5 Tang, Shaojie
5 Teiller, Alexandre
5 Verschae, José
5 Vondrák, Jan
5 Zschoche, Philipp
4 Adamczyk, Marek
4 Ahmed, Reyan
...and 1,824 more Authors
all top 5

Cited in 167 Serials

92 Algorithmica
75 Theoretical Computer Science
57 SIAM Journal on Computing
35 Mathematical Programming. Series A. Series B
28 Operations Research Letters
27 Discrete Applied Mathematics
27 Information Processing Letters
27 Journal of Combinatorial Optimization
25 SIAM Journal on Discrete Mathematics
21 Mathematics of Operations Research
20 Journal of Computer and System Sciences
19 Discrete & Computational Geometry
16 Operations Research
15 European Journal of Operational Research
15 Theory of Computing Systems
12 Networks
11 Journal of Machine Learning Research (JMLR)
9 Discrete Optimization
8 Computers & Operations Research
8 Distributed Computing
7 INFORMS Journal on Computing
7 Journal of Scheduling
6 ACM Transactions on Algorithms
5 The Annals of Statistics
5 Games and Economic Behavior
5 Optimization Letters
4 Linear Algebra and its Applications
4 SIAM Journal on Optimization
4 Computational Optimization and Applications
4 Foundations of Computational Mathematics
4 Journal of Discrete Algorithms
3 Artificial Intelligence
3 Information Sciences
3 Journal of the American Statistical Association
3 Journal of Computational and Applied Mathematics
3 Information and Computation
3 Annals of Operations Research
3 Machine Learning
3 Random Structures & Algorithms
3 Computational Geometry
3 Journal of Global Optimization
3 Applied and Computational Harmonic Analysis
3 The Journal of Artificial Intelligence Research (JAIR)
3 Optimization Methods & Software
3 Journal of the ACM
3 Algorithms
3 Information and Inference
3 Journal of the Operations Research Society of China
2 Communications in Mathematical Physics
2 Discrete Mathematics
2 Applied Mathematics and Optimization
2 Illinois Journal of Mathematics
2 Journal of Combinatorial Theory. Series B
2 Journal of Functional Analysis
2 Proceedings of the American Mathematical Society
2 Combinatorica
2 SIAM Journal on Matrix Analysis and Applications
2 International Journal of Computational Geometry & Applications
2 The Annals of Applied Probability
2 Computational Statistics and Data Analysis
2 Top
2 Positivity
2 Data Mining and Knowledge Discovery
2 International Journal of Applied Mathematics and Computer Science
2 Optimization and Engineering
2 RAIRO. Operations Research
2 Journal of Industrial and Management Optimization
2 Mathematical Programming Computation
2 Journal of Computational and Graphical Statistics
2 Statistics and Computing
2 Stochastic Systems
2 EURO Journal on Computational Optimization
2 Analysis and Geometry in Metric Spaces
2 SIAM Journal on Mathematics of Data Science
1 ACM Computing Surveys
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 Physica A
1 Acta Mathematica
1 Advances in Mathematics
1 The Annals of Probability
1 Applied Mathematics and Computation
1 Automatica
1 BIT
1 Bulletin of the London Mathematical Society
1 Canadian Journal of Mathematics
1 Geometriae Dedicata
1 Inventiones Mathematicae
1 Journal of Econometrics
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 Results in Mathematics
1 Transactions of the American Mathematical Society
...and 67 more Serials
all top 5

Cited in 38 Fields

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

Citations by Year