×

zbMATH — the first resource for mathematics

Bansal, Nikhil

Compute Distance To:
Author ID: bansal.nikhil Recent zbMATH articles by "Bansal, Nikhil"
Published as: Bansal, Nikhil; Bansal, N.
External Links: MGP
Documents Indexed: 151 Publications since 1996, including 2 Books
all top 5

Co-Authors

8 single-authored
24 Pruhs, Kirk R.
19 Nagarajan, Viswanath
16 Sviridenko, Maxim I.
13 Naor, Joseph Seffi
12 Chan, Ho-Leung
10 Gupta, Anupam
8 Buchbinder, Niv
7 Eliáš, Marek
7 Koumoutsos, Grigorios
7 Krishnaswamy, Ravishankar
6 Garg, Shashwat
6 Khandekar, Rohit
6 Schieber, Baruch
5 Coppersmith, Don
5 Dhamdhere, Kedar
4 Jeż, Łukasz
4 Kimbrel, Tracy
4 Könemann, Jochen
4 Nederlof, Jesper
4 Srinivasan, Aravind
4 Stein, Clifford
4 Umboh, Seeun William
3 Blum, Avrim L.
3 Chawla, Shuchi
3 Dadush, Daniel
3 Guruganesh, Guru Prashanth
3 Pendavingh, Rudi A.
3 Rudra, Atri
3 Schwartz, Roy
3 Spencer, Joel H.
3 Van der Pol, Jorn G.
3 van der Zwaan, Ruben
3 Vredeveld, Tjark
2 Böhm, Martin
2 Bunde, David P.
2 Caprara, Alberto
2 Charikar, Moses S.
2 Chen, Ning
2 Cherniavsky, Neva
2 Cieliebak, Mark
2 Cloostermans, Bouke
2 Feige, Uriel
2 Finocchi, Irene
2 Friggstad, Zachary
2 Han, Xin
2 Harchol-Balter, Mor
2 Iwama, Kazuo
2 Khan, Arindam
2 Khot, Subhash Ajit
2 Korula, Nitish
2 Krauthgamer, Robert
2 Lee, Kang-Won
2 Lipták, Zsuzsanna
2 Lovett, Shachar
2 Mądry, Aleksander
2 Mahdian, Mohammad
2 Makarychev, Konstantin S.
2 Meka, Raghu
2 Mestre, Julián
2 Peis, Britta
2 Salavatipour, Mohammad R.
2 Sinha, Amitabh
2 Svensson, Ola
2 Vyas, Nikhil
2 Williams, Richard Ryan
2 Zafer, Murtaza
2 Zhang, Guochuan
1 Abbasi-Zadeh, Sepehr
1 Agrawal, Mukesh
1 Balcan, Maria-Florina
1 Beygelzimer, Alina
1 Bhatt, Vibhor
1 Bravyi, Sergey B.
1 Casper, N.
1 Chakrabarti, Amit
1 Chalermsook, Parinya
1 Chen, Danny Ziyi
1 Correa, José R.
1 Dürr, Christoph
1 Eliéš, Marek
1 Epstein, Amir
1 Fleischer, Lisa K.
1 Gamarnik, David
1 Hamedani, Hooman G.
1 Hu, Xiaobo Sharon
1 Jansen, Klaus
1 Jayanti, Prasad
1 Jiang, Haotian
1 Kamphorst, Bart
1 Kazeykina, Anna
1 Kenyon, Claire M.
1 Khanna, Sanjeev
1 Kondapally, Ranganath
1 Kulkarni, Janardhan
1 Laekhanukit, Bundit
1 Lam, Tak-Wah
1 Langford, John
1 Lee, Lap-Kei
1 Lewenstein, Moshe
1 Li, Shi
...and 29 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

119 Publications have been cited 941 times in 694 Documents Cited by Year
Correlation clustering. Zbl 1089.68085
Bansal, Nikhil; Blum, Avrim; Chawla, Shuchi
109
2004
Speed scaling to manage energy and temperature. Zbl 1326.68043
Bansal, Nikhil; Kimbrel, Tracy; Pruhs, Kirk
53
2007
The Santa Claus problem. Zbl 1301.90057
Bansal, Nikhil; Sviridenko, Maxim
44
2006
Bin packing in multiple dimensions: inapproximability results and approximation schemes. Zbl 1278.90324
Bansal, Nikhil; Correa, José R.; Kenyon, Claire; Sviridenko, Maxim
35
2006
A quasi-PTAS for unsplittable flow on line graphs. Zbl 1301.68264
Bansal, Nikhil; Chakrabarti, Amit; Epstein, Amir; Schieber, Baruch
28
2006
Upper bounds for MaxSat: Further improved. Zbl 0971.68069
Bansal, Nikhil; Raman, Venkatesh
25
1999
Scheduling for speed bounded processors. Zbl 1153.68334
Bansal, Nikhil; Chan, Ho-Leung; Lam, Tak-Wah; Lee, Lap-Kei
24
2008
Approximation algorithms for deadline-TSP and vehicle routing with time-windows. Zbl 1192.90216
Bansal, Nikhil; Blum, Avrim; Chawla, Shuchi; Meyerson, Adam
24
2004
Additive guarantees for degree-bounded directed network design. Zbl 1206.68366
Bansal, Nikhil; Khandekar, Rohit; Nagarajan, Viswanath
21
2009
Speed scaling with an arbitrary power function. Zbl 1301.90026
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
20
2013
Inapproximability of hypergraph vertex cover and applications to scheduling problems. Zbl 1287.90018
Bansal, Nikhil; Khot, Subhash
18
2010
A new approximation method for set covering problems, with applications to multidimensional bin packing. Zbl 1201.90071
Bansal, Nikhil; Caprara, Alberto; Sviridenko, Maxim
17
2009
Optimal long code test with one free bit. Zbl 1292.68081
Bansal, Nikhil; Khot, Subhash
16
2009
A primal-dual randomized algorithm for weighted paging. Zbl 1281.68238
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
15
2012
Speed scaling for weighted flow time. Zbl 1302.68036
Bansal, Nikhil; Pruhs, Kirk; Stein, Cliff
14
2007
The geometry of scheduling. Zbl 1335.90031
Bansal, Nikhil; Pruhs, Kirk
14
2014
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
14
2012
Improved bounds for speed scaling in devices obeying the cube-root rule. Zbl 1248.68107
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk; Katz, Dmitriy
13
2009
Speed scaling for weighted flow time. Zbl 1213.68196
Bansal, Nikhil; Pruhs, Kirk; Stein, Cliff
13
2009
Regularity lemmas and combinatorial algorithms. Zbl 1292.05242
Bansal, Nikhil; Williams, Ryan
13
2009
Server scheduling to balance priorities, fairness, and average quality of service. Zbl 1209.68058
Bansal, Nikhil; Pruhs, Kirk R.
12
2010
On the number of matroids. Zbl 1363.05005
Bansal, Nikhil; Pendavingh, Rudi A.; Van der Pol, Jorn G.
12
2015
New approximability and inapproximability results for 2-dimensional bin packing. Zbl 1317.68269
Bansal, Nikhil; Sviridenko, Maxim
11
2004
A logarithmic approximation for unsplittable flow on line graphs. Zbl 1321.68493
Bansal, Nikhil; Friggstad, Zachary; Khandekar, Rohit; Salavatipour, Mohammad R.
11
2014
A constant factor approximation algorithm for generalized MIN-sum set cover. Zbl 1288.68254
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar
11
2010
On generalizations of network design problems with degree bounds. Zbl 1295.90059
Bansal, Nikhil; Khandekar, Rohit; Könemann, Jochen; Nagarajan, Viswanath; Peis, Britta
11
2013
Randomized competitive algorithms for generalized caching. Zbl 1231.68278
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
10
2008
Harmonic algorithm for \(3\)-dimensional strip packing problem. Zbl 1302.90165
Bansal, Nikhil; Han, Xin; Iwama, Kazuo; Sviridenko, Maxim; Zhang, Guochuan
9
2007
Analysis of the M/G/1 processor-sharing queue with bulk arrivals. Zbl 1024.60039
Bansal, Nikhil
9
2003
Minimizing weighted flow time. Zbl 1092.68540
Bansal, N.; Dhamdhere, K.
9
2003
Further improvements in competitive guarantees for QoS buffering. Zbl 1098.68516
Bansal, Nikhil; Fleischer, Lisa K.; Kimbrel, Tracy; Mahdian, Mohammad; Schieber, Baruch; Sviridenko, Maxim
9
2004
Minimizing setup and beam-on times in radiation therapy. Zbl 1155.92325
Bansal, Nikhil; Coppersmith, Don; Schieber, Baruch
9
2006
Speed scaling to manage temperature. Zbl 1118.68769
Bansal, Nikhil; Pruhs, Kirk
9
2005
Randomized competitive algorithms for generalized caching. Zbl 1252.68355
Bansal, Nikhil; Naor, Joseph (Seffi)
8
2012
On \(k\)-column sparse packing programs. Zbl 1285.90013
Bansal, Nikhil; Korula, Nitish; Nagarajan, Viswanath; Srinivasan, Aravind
8
2010
Server scheduling in the \(L_p\) norm: a rising tide lifts all boat. Zbl 1192.90062
Bansal, Nikhil; Pruhs, Kirk
8
2003
A polylogarithmic-competitive algorithm for the \(k\)-server problem (extended abstract). Zbl 1292.68153
Bansal, Nikhil; Buchbinder, Niv; Mądry, Aleksander; Naor, Joseph
8
2011
Speed scaling with an arbitrary power function. Zbl 1422.68017
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
8
2009
SRPT scheduling for web servers. Zbl 1056.68610
Harchol-Balter, Mor; Bansal, Nikhil; Schroeder, Bianca; Agrawal, Mukesh
7
2001
Server scheduling in the weighted \(\ell_p\) norm. Zbl 1196.68027
Bansal, Nikhil; Pruhs, Kirk
7
2004
Average rate speed scaling. Zbl 1136.68348
Bansal, Nikhil; Bunde, David P.; Chan, Ho-Leung; Pruhs, Kirk
7
2008
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
Average rate speed scaling. Zbl 1216.68060
Bansal, Nikhil; Bunde, David P.; Chan, Ho-Leung; Pruhs, Kirk
7
2011
Solving packing integer programs via randomized rounding with alterations. Zbl 1297.68259
Bansal, Nikhil; Korula, Nitish; Nagarajan, Viswanath; Srinivasan, Aravind
7
2012
Regularity lemmas and combinatorial algorithms. Zbl 1253.68162
Bansal, Nikhil; Williams, Ryan
7
2012
A structural lemma in 2-dimensional packing, and its implications on approximability. Zbl 1272.52018
Bansal, Nikhil; Caprara, Alberto; Jansen, Klaus; Prädel, Lars; Sviridenko, Maxim
6
2009
Minimizing makespan in no-wait job shops. Zbl 1278.90141
Bansal, Nikhil; Mahdian, Mohammad; Sviridenko, Maxim
6
2005
Job shop scheduling with unit processing times. Zbl 1278.90140
Bansal, Nikhil; Kimbrel, Tracy; Sviridenko, Maxim
6
2006
Additive guarantees for degree bounded directed network design. Zbl 1231.68046
Bansal, Nikhil; Khandekar, Rohit; Nagarajan, Viswanath
6
2008
Lift-and-round to improve weighted completion time on unrelated machines. Zbl 1373.68151
Bansal, Nikhil; Srinivasan, Aravind; Svensson, Ola
5
2016
Handling load with less stress. Zbl 1101.90016
Bansal, Nikhil; Gamarnik, David
5
2006
Better scalable algorithms for broadcast scheduling. Zbl 1288.68284
Bansal, Nikhil; Krishnaswamy, Ravishankar; Nagarajan, Viswanath
5
2010
On the Lovász theta function for independent sets in sparse graphs. Zbl 1321.05176
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru
5
2015
Minimum congestion mapping in a cloud. Zbl 1321.68446
Bansal, Nikhil; Lee, Kang-Won; Nagarajan, Viswanath; Zafer, Murtaza
5
2011
Min-max graph partitioning and small set expansion. Zbl 1292.05126
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy
5
2011
Improved bounds for speed scaling in devices obeying the cube-root rule. Zbl 1253.68068
Bansal, Nikhil; Chan, Ho-Leung; Katz, Dmitriy; Pruhs, Kirk
5
2012
Robust reductions from ranking to classification. Zbl 1203.68135
Balcan, Maria-Florina; Bansal, Nikhil; Beygelzimer, Alina; Coppersmith, Don; Langford, John; Sorkin, Gregory B.
4
2007
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 the randomized \(k\)-server conjecture, a primal-dual approach. Zbl 1288.68283
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
4
2010
On the adaptivity gap of stochastic orienteering. Zbl 1415.90046
Bansal, Nikhil; Nagarajan, Viswanath
4
2014
Weighted flow time does not admit \(O(1)\)-competitive algorithms. Zbl 1422.90017
Bansal, Nikhil; Chan, Ho-Leung
4
2009
Non-clairvoyant scheduling for minimizing mean slowdown. Zbl 1035.68504
Bansal, N.; Dhamdhere, K.; Könemann, J.; Sinha, A.
3
2003
Non-clairvoyant scheduling for minimizing mean slowdown. Zbl 1082.68010
Bansal, Nikhil; Dhamdhere, Kedar; Könemann, Jochen; Sinha, Amitabh
3
2004
On the average sojourn time under \(M/M/1/\)SRPT. Zbl 1099.90014
Bansal, Nikhil
3
2005
Scheduling for flow-time with admission control. Zbl 1266.68067
Bansal, Nikhil; Blum, Avrim; Chawla, Shuchi; Dhamdhere, Kedar
3
2003
Improved approximation algorithms for broadcast scheduling. Zbl 1192.90061
Bansal, Nikhil; Coppersmith, Don; Sviridenko, Maxim
3
2006
Metrical task systems and the \(k\)-server problem on HSTs. Zbl 1288.68282
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
3
2010
Tight approximation bounds for dominating set on graphs of bounded arboricity. Zbl 1422.68291
Bansal, Nikhil; Umboh, Seeun William
3
2017
Approximating the average response time in broadcast scheduling. Zbl 1297.68038
Bansal, Nikhil; Charikar, Moses; Khanna, Sanjeev; Naor, Joseph (Seffi)
3
2005
Minimizing weighted flow time. Zbl 1445.90029
Bansal, Nikhil; Dhamdhere, Kedar
3
2007
Min-max graph partitioning and small set expansion. Zbl 1360.68639
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph (Seffi); Schwartz, Roy
3
2014
Algorithmic discrepancy beyond partial coloring. Zbl 1369.68229
Bansal, Nikhil; Garg, Shashwat
3
2017
Weighted geometric set multi-cover via quasi-uniform sampling. Zbl 1365.68436
Bansal, Nikhil; Pruhs, Kirk
3
2012
A harmonic algorithm for the 3D strip packing problem. Zbl 1271.68250
Bansal, Nikhil; Han, Xin; Iwama, Kazuo; Sviridenko, Maxim; Zhang, Guochuan
3
2013
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
On capacitated set cover problems. Zbl 1343.90074
Bansal, Nikhil; Krishnaswamy, Ravishankar; Saha, Barna
3
2011
A logarithmic approximation for unsplittable flow on line graphs. Zbl 1422.68289
Bansal, Nikhil; Friggstad, Zachary; Khandekar, Rohit; Salavatipour, Mohammad R.
3
2009
Better algorithms and hardness for broadcast scheduling via a discrepancy approach. Zbl 1422.68288
Bansal, Nikhil; Charikar, Moses; Krishnaswamy, Ravishankar; Li, Shi
3
2014
Minimum congestion mapping in a cloud. Zbl 1325.68026
Bansal, Nikhil; Lee, Kang-Won; Nagarajan, Viswanath; Zafer, Murtaza
2
2015
A note on comparing response times in the \(M/GI/1/FB\) and \(M/GI/1/PS\) queues. Zbl 1135.90328
Wierman, Adam; Bansal, Nikhil; Harchol-Balter, Mor
2
2004
Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs. Zbl 1180.82016
Bansal, Nikhil; Bravyi, Sergey; Terhal, Barbara M.
2
2009
Two-dimensional bin packing with one-dimensional resource augmentation. Zbl 1278.90325
Bansal, Nikhil; Sviridenko, Maxim
2
2007
Speed scaling with a solar cell. Zbl 1187.68105
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
2
2009
On generalizations of network design problems with degree bounds. Zbl 1285.90044
Bansal, Nikhil; Khandekar, Rohit; Könemann, Jochen; Nagarajan, Viswanath; Peis, Britta
2
2010
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
Dynamic pricing for impatient bidders. Zbl 1300.91031
Bansal, Nikhil; Chen, Ning; Cherniavsky, Neva; Rurda, Atri; Schieber, Baruch; Sviridenko, Maxim
2
2010
A polylogarithmic-competitive algorithm for the \(k\)-server problem. Zbl 1426.68294
Bansal, Nikhil; Buchbinder, Niv; Madry, Aleksander; Naor, Joseph (Seffi)
2
2015
Approximation-friendly discrepancy rounding. Zbl 1419.90066
Bansal, Nikhil; Nagarajan, Viswanath
2
2016
Minimizing flow-time on unrelated machines. Zbl 1321.68113
Bansal, Nikhil; Kulkarni, Janardhan
2
2015
On the adaptivity gap of stochastic orienteering. Zbl 1337.90019
Bansal, Nikhil; Nagarajan, Viswanath
2
2015
Approximating vector scheduling: almost matching upper and lower bounds. Zbl 1355.68292
Bansal, Nikhil; Oosterwijk, Tim; Vredeveld, Tjark; van der Zwaan, Ruben
2
2016
Weighted geometric set multi-cover via quasi-uniform sampling. Zbl 1405.68396
Bansal, Nikhil; Pruhs, Kirk
2
2016
Faster space-efficient algorithms for subset sum and \(k\)-sum. Zbl 1369.68348
Bansal, Nikhil; Garg, Shashwat; Nederlof, Jesper; Vyas, Nikhil
2
2017
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
2
2015
The local-global conjecture for scheduling with non-linear cost. Zbl 1376.90022
Bansal, Nikhil; Dürr, Christoph; Thang, Nguyen Kim; Vásquez, Óscar C.
2
2017
Approximating independent sets in sparse graphs. Zbl 1372.68295
Bansal, Nikhil
2
2015
Improved approximation algorithm for two-dimensional bin packing. Zbl 1422.68290
Bansal, Nikhil; Khan, Arindam
2
2014
Dynamic pricing for impatient bidders. Zbl 1303.91077
Bansal, Nikhil; Chen, Ning; Cherniavsky, Neva; Rudra, Atri; Schieber, Baruch; Sviridenko, Maxim
1
2007
Minimizing flow time on a constant number of machines with preemption. Zbl 1140.90389
Bansal, Nikhil
1
2005
Competitive algorithms for due date scheduling. Zbl 1171.90390
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
1
2007
The \((h,k)\)-server problem on bounded depth trees. Zbl 1454.68189
Bansal, Nikhil; Eliéš, Marek; Jeż, Łukasz; Koumoutsos, Grigorios
1
2019
Competitive algorithms for generalized \(k\)-server in uniform metrics. Zbl 1403.68357
Bansal, Nikhil; Eliáš, Marek; Koumoutsos, Grigorios; Nederlof, Jesper
1
2018
Nested convex bodies are chaseable. Zbl 1403.68313
Bansal, Nikhil; Böhm, Martin; Eliáš, Marek; Koumoutsos, Grigorios; Umboh, Seeun William
1
2018
Tight bounds for double coverage against weak adversaries. Zbl 1390.68767
Bansal, Nikhil; Eliáš, Marek; Jeż, Łukasz; Koumoutsos, Grigorios; Pruhs, Kirk
1
2018
The Gram-Schmidt walk: a cure for the Banaszczyk blues. Zbl 1427.68328
Bansal, Nikhil; Dadush, Daniel; Garg, Shashwat; Lovett, Shachar
1
2018
Achievable performance of blind policies in heavy traffic. Zbl 1433.60086
Bansal, Nikhil; Kamphorst, Bart; Zwart, Bert
1
2018
Tight approximation bounds for dominating set on graphs of bounded arboricity. Zbl 1422.68291
Bansal, Nikhil; Umboh, Seeun William
3
2017
Algorithmic discrepancy beyond partial coloring. Zbl 1369.68229
Bansal, Nikhil; Garg, Shashwat
3
2017
Faster space-efficient algorithms for subset sum and \(k\)-sum. Zbl 1369.68348
Bansal, Nikhil; Garg, Shashwat; Nederlof, Jesper; Vyas, Nikhil
2
2017
The local-global conjecture for scheduling with non-linear cost. Zbl 1376.90022
Bansal, Nikhil; Dürr, Christoph; Thang, Nguyen Kim; Vásquez, Óscar C.
2
2017
Approximation-friendly discrepancy rounding. Zbl 1411.90219
Bansal, Nikhil; Nagarajan, Viswanath
1
2017
Lift-and-round to improve weighted completion time on unrelated machines. Zbl 1373.68151
Bansal, Nikhil; Srinivasan, Aravind; Svensson, Ola
5
2016
Approximation-friendly discrepancy rounding. Zbl 1419.90066
Bansal, Nikhil; Nagarajan, Viswanath
2
2016
Approximating vector scheduling: almost matching upper and lower bounds. Zbl 1355.68292
Bansal, Nikhil; Oosterwijk, Tim; Vredeveld, Tjark; van der Zwaan, Ruben
2
2016
Weighted geometric set multi-cover via quasi-uniform sampling. Zbl 1405.68396
Bansal, Nikhil; Pruhs, Kirk
2
2016
Improved approximation for vector bin packing. Zbl 1414.90301
Bansal, Nikhil; Eliáš, Marek; Khan, Arindam
1
2016
Minimizing maximum flow-time on related machines. Zbl 1391.90239
Bansal, Nikhil; Cloostermans, Bouke
1
2016
On the number of matroids. Zbl 1363.05005
Bansal, Nikhil; Pendavingh, Rudi A.; Van der Pol, Jorn G.
12
2015
On the Lovász theta function for independent sets in sparse graphs. Zbl 1321.05176
Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru
5
2015
Minimum congestion mapping in a cloud. Zbl 1325.68026
Bansal, Nikhil; Lee, Kang-Won; Nagarajan, Viswanath; Zafer, Murtaza
2
2015
A polylogarithmic-competitive algorithm for the \(k\)-server problem. Zbl 1426.68294
Bansal, Nikhil; Buchbinder, Niv; Madry, Aleksander; Naor, Joseph (Seffi)
2
2015
Minimizing flow-time on unrelated machines. Zbl 1321.68113
Bansal, Nikhil; Kulkarni, Janardhan
2
2015
On the adaptivity gap of stochastic orienteering. Zbl 1337.90019
Bansal, Nikhil; Nagarajan, Viswanath
2
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
2
2015
Approximating independent sets in sparse graphs. Zbl 1372.68295
Bansal, Nikhil
2
2015
Algorithms – ESA 2015. 23rd annual European symposium, Patras, Greece, September 14–16, 2015. Proceedings. Zbl 1320.68011
Bansal, Nikhil; Finocchi, Irene
1
2015
The geometry of scheduling. Zbl 1335.90031
Bansal, Nikhil; Pruhs, Kirk
14
2014
A logarithmic approximation for unsplittable flow on line graphs. Zbl 1321.68493
Bansal, Nikhil; Friggstad, Zachary; Khandekar, Rohit; Salavatipour, Mohammad R.
11
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
On the adaptivity gap of stochastic orienteering. Zbl 1415.90046
Bansal, Nikhil; Nagarajan, Viswanath
4
2014
Min-max graph partitioning and small set expansion. Zbl 1360.68639
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph (Seffi); Schwartz, Roy
3
2014
Better algorithms and hardness for broadcast scheduling via a discrepancy approach. Zbl 1422.68288
Bansal, Nikhil; Charikar, Moses; Krishnaswamy, Ravishankar; Li, Shi
3
2014
Improved approximation algorithm for two-dimensional bin packing. Zbl 1422.68290
Bansal, Nikhil; Khan, Arindam
2
2014
An entropy argument for counting matroids. Zbl 1301.05055
Bansal, N.; Pendavingh, R. A.; van der Pol, J. G.
1
2014
Better scalable algorithms for broadcast scheduling. Zbl 1398.68060
Bansal, Nikhil; Krishnaswamy, Ravishankar; Nagarajan, Viswanath
1
2014
Approximating vector scheduling: almost matching upper and lower bounds. Zbl 1351.68305
Bansal, Nikhil; Vredeveld, Tjark; van der Zwaan, Ruben
1
2014
Speed scaling with an arbitrary power function. Zbl 1301.90026
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
20
2013
On generalizations of network design problems with degree bounds. Zbl 1295.90059
Bansal, Nikhil; Khandekar, Rohit; Könemann, Jochen; Nagarajan, Viswanath; Peis, Britta
11
2013
A harmonic algorithm for the 3D strip packing problem. Zbl 1271.68250
Bansal, Nikhil; Han, Xin; Iwama, Kazuo; Sviridenko, Maxim; Zhang, Guochuan
3
2013
On the number of matroids. Zbl 1422.05030
Bansal, Nikhil; Pendavingh, Rudi A.; van der Pol, Jorn G.
1
2013
A primal-dual randomized algorithm for weighted paging. Zbl 1281.68238
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
15
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
14
2012
Randomized competitive algorithms for generalized caching. Zbl 1252.68355
Bansal, Nikhil; Naor, Joseph (Seffi)
8
2012
Solving packing integer programs via randomized rounding with alterations. Zbl 1297.68259
Bansal, Nikhil; Korula, Nitish; Nagarajan, Viswanath; Srinivasan, Aravind
7
2012
Regularity lemmas and combinatorial algorithms. Zbl 1253.68162
Bansal, Nikhil; Williams, Ryan
7
2012
Improved bounds for speed scaling in devices obeying the cube-root rule. Zbl 1253.68068
Bansal, Nikhil; Chan, Ho-Leung; Katz, Dmitriy; Pruhs, Kirk
5
2012
Weighted geometric set multi-cover via quasi-uniform sampling. Zbl 1365.68436
Bansal, Nikhil; Pruhs, Kirk
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
A polylogarithmic-competitive algorithm for the \(k\)-server problem (extended abstract). Zbl 1292.68153
Bansal, Nikhil; Buchbinder, Niv; Mądry, Aleksander; Naor, Joseph
8
2011
Average rate speed scaling. Zbl 1216.68060
Bansal, Nikhil; Bunde, David P.; Chan, Ho-Leung; Pruhs, Kirk
7
2011
Minimum congestion mapping in a cloud. Zbl 1321.68446
Bansal, Nikhil; Lee, Kang-Won; Nagarajan, Viswanath; Zafer, Murtaza
5
2011
Min-max graph partitioning and small set expansion. Zbl 1292.05126
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy
5
2011
On capacitated set cover problems. Zbl 1343.90074
Bansal, Nikhil; Krishnaswamy, Ravishankar; Saha, Barna
3
2011
Shape rectangularization problems in intensity-modulated radiation therapy. Zbl 1215.68245
Bansal, Nikhil; Chen, Danny Z.; Coppersmith, Don; Hu, Xiaobo S.; Luan, Shuang; Misiołek, Ewa; Schieber, Baruch; Wang, Chao
1
2011
Deterministic discrepancy minimization. Zbl 1308.90124
Bansal, Nikhil; Spencer, Joel
1
2011
Inapproximability of hypergraph vertex cover and applications to scheduling problems. Zbl 1287.90018
Bansal, Nikhil; Khot, Subhash
18
2010
Server scheduling to balance priorities, fairness, and average quality of service. Zbl 1209.68058
Bansal, Nikhil; Pruhs, Kirk R.
12
2010
A constant factor approximation algorithm for generalized MIN-sum set cover. Zbl 1288.68254
Bansal, Nikhil; Gupta, Anupam; Krishnaswamy, Ravishankar
11
2010
On \(k\)-column sparse packing programs. Zbl 1285.90013
Bansal, Nikhil; Korula, Nitish; Nagarajan, Viswanath; Srinivasan, Aravind
8
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
Better scalable algorithms for broadcast scheduling. Zbl 1288.68284
Bansal, Nikhil; Krishnaswamy, Ravishankar; Nagarajan, Viswanath
5
2010
Towards the randomized \(k\)-server conjecture, a primal-dual approach. Zbl 1288.68283
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
4
2010
Metrical task systems and the \(k\)-server problem on HSTs. Zbl 1288.68282
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
3
2010
On generalizations of network design problems with degree bounds. Zbl 1285.90044
Bansal, Nikhil; Khandekar, Rohit; Könemann, Jochen; Nagarajan, Viswanath; Peis, Britta
2
2010
Dynamic pricing for impatient bidders. Zbl 1300.91031
Bansal, Nikhil; Chen, Ning; Cherniavsky, Neva; Rurda, Atri; Schieber, Baruch; Sviridenko, Maxim
2
2010
On the longest common rigid subsequence problem. Zbl 1191.68216
Bansal, Nikhil; Lewenstein, Moshe; Ma, Bin; Zhang, Kaizhong
1
2010
Additive guarantees for degree-bounded directed network design. Zbl 1206.68366
Bansal, Nikhil; Khandekar, Rohit; Nagarajan, Viswanath
21
2009
A new approximation method for set covering problems, with applications to multidimensional bin packing. Zbl 1201.90071
Bansal, Nikhil; Caprara, Alberto; Sviridenko, Maxim
17
2009
Optimal long code test with one free bit. Zbl 1292.68081
Bansal, Nikhil; Khot, Subhash
16
2009
Improved bounds for speed scaling in devices obeying the cube-root rule. Zbl 1248.68107
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk; Katz, Dmitriy
13
2009
Speed scaling for weighted flow time. Zbl 1213.68196
Bansal, Nikhil; Pruhs, Kirk; Stein, Cliff
13
2009
Regularity lemmas and combinatorial algorithms. Zbl 1292.05242
Bansal, Nikhil; Williams, Ryan
13
2009
Speed scaling with an arbitrary power function. Zbl 1422.68017
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
8
2009
A structural lemma in 2-dimensional packing, and its implications on approximability. Zbl 1272.52018
Bansal, Nikhil; Caprara, Alberto; Jansen, Klaus; Prädel, Lars; Sviridenko, Maxim
6
2009
Weighted flow time does not admit \(O(1)\)-competitive algorithms. Zbl 1422.90017
Bansal, Nikhil; Chan, Ho-Leung
4
2009
A logarithmic approximation for unsplittable flow on line graphs. Zbl 1422.68289
Bansal, Nikhil; Friggstad, Zachary; Khandekar, Rohit; Salavatipour, Mohammad R.
3
2009
Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs. Zbl 1180.82016
Bansal, Nikhil; Bravyi, Sergey; Terhal, Barbara M.
2
2009
Speed scaling with a solar cell. Zbl 1187.68105
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
2
2009
Scheduling for speed bounded processors. Zbl 1153.68334
Bansal, Nikhil; Chan, Ho-Leung; Lam, Tak-Wah; Lee, Lap-Kei
24
2008
Randomized competitive algorithms for generalized caching. Zbl 1231.68278
Bansal, Nikhil; Buchbinder, Niv; Naor, Joseph (Seffi)
10
2008
Average rate speed scaling. Zbl 1136.68348
Bansal, Nikhil; Bunde, David P.; Chan, Ho-Leung; Pruhs, Kirk
7
2008
Additive guarantees for degree bounded directed network design. Zbl 1231.68046
Bansal, Nikhil; Khandekar, Rohit; Nagarajan, Viswanath
6
2008
Improved approximation algorithms for broadcast scheduling. Zbl 1187.68704
Bansal, Nikhil; Coppersmith, Don; Sviridenko, Maxim
1
2008
Speed scaling to manage energy and temperature. Zbl 1326.68043
Bansal, Nikhil; Kimbrel, Tracy; Pruhs, Kirk
53
2007
Speed scaling for weighted flow time. Zbl 1302.68036
Bansal, Nikhil; Pruhs, Kirk; Stein, Cliff
14
2007
Harmonic algorithm for \(3\)-dimensional strip packing problem. Zbl 1302.90165
Bansal, Nikhil; Han, Xin; Iwama, Kazuo; Sviridenko, Maxim; Zhang, Guochuan
9
2007
Robust reductions from ranking to classification. Zbl 1203.68135
Balcan, Maria-Florina; Bansal, Nikhil; Beygelzimer, Alina; Coppersmith, Don; Langford, John; Sorkin, Gregory B.
4
2007
Minimizing weighted flow time. Zbl 1445.90029
Bansal, Nikhil; Dhamdhere, Kedar
3
2007
Two-dimensional bin packing with one-dimensional resource augmentation. Zbl 1278.90325
Bansal, Nikhil; Sviridenko, Maxim
2
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
Dynamic pricing for impatient bidders. Zbl 1303.91077
Bansal, Nikhil; Chen, Ning; Cherniavsky, Neva; Rudra, Atri; Schieber, Baruch; Sviridenko, Maxim
1
2007
Competitive algorithms for due date scheduling. Zbl 1171.90390
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
1
2007
The Santa Claus problem. Zbl 1301.90057
Bansal, Nikhil; Sviridenko, Maxim
44
2006
Bin packing in multiple dimensions: inapproximability results and approximation schemes. Zbl 1278.90324
Bansal, Nikhil; Correa, José R.; Kenyon, Claire; Sviridenko, Maxim
35
2006
A quasi-PTAS for unsplittable flow on line graphs. Zbl 1301.68264
Bansal, Nikhil; Chakrabarti, Amit; Epstein, Amir; Schieber, Baruch
28
2006
Minimizing setup and beam-on times in radiation therapy. Zbl 1155.92325
Bansal, Nikhil; Coppersmith, Don; Schieber, Baruch
9
2006
Job shop scheduling with unit processing times. Zbl 1278.90140
Bansal, Nikhil; Kimbrel, Tracy; Sviridenko, Maxim
6
2006
Handling load with less stress. Zbl 1101.90016
Bansal, Nikhil; Gamarnik, David
5
2006
Improved approximation algorithms for broadcast scheduling. Zbl 1192.90061
Bansal, Nikhil; Coppersmith, Don; Sviridenko, Maxim
3
2006
Speed scaling to manage temperature. Zbl 1118.68769
Bansal, Nikhil; Pruhs, Kirk
9
2005
...and 19 more Documents
all top 5

Cited by 1,202 Authors

25 Epstein, Leah
21 Bansal, Nikhil
19 Nagarajan, Viswanath
16 Pruhs, Kirk R.
15 Levin, Asaf
12 Moseley, Benjamin
11 Im, Sungjin
11 van Stee, Rob
10 Antoniadis, Antonios Foivos
10 Jansen, Klaus
10 Niedermeier, Rolf
9 Komusiewicz, Christian
9 Li, Minming
9 Mastrolilli, Monaldo
9 Wiese, Andreas
9 Wong, Prudence Wai-Ha
8 Bampis, Evripidis
8 Guo, Jiong
8 Zenklusen, Rico
7 Albers, Susanne
7 Kumar, Amit
7 Lam, Tak-Wah
7 Lingas, Andrzej
7 Singh, Mohit
7 Svensson, Ola
7 Sviridenko, Maxim I.
6 Chen, Jian-er
6 Chin, Francis Y. L.
6 Gupta, Anupam
6 Khandekar, Rohit
6 Letsios, Dimitrios
6 Lucarelli, Giorgio
6 Nutov, Zeev
6 Uhlmann, Johannes
6 Zhang, Yong
5 Bulhões Júnior, Teobaldo Leite
5 Chan, Ho-Leung
5 Fukunaga, Takuro
5 Fung, Stanley P. Y.
5 Garg, Naveen Kumar
5 Grandoni, Fabrizio
5 Han, Xin
5 Könemann, Jochen
5 Krishnaswamy, Ravishankar
5 Kurpisz, Adam
5 Lau, Lap Chi
5 Lee, Lap-Kei
5 Ravi, Ramamoorthi
5 Ting, Hing-Fung
5 Van der Pol, Jorn G.
4 Angel, Eric
4 Ayesta, Urtzi
4 Azar, Yossi
4 Barcelo, Neal
4 Cao, Yixin
4 Correa, José R.
4 de Sousa Filho, Gilberto F.
4 dos Anjos F. Cabral, Lucidio
4 Dürr, Christoph
4 Guruswami, Venkatesan
4 Harren, Rolf
4 Il’ev, Victor Petrovich
4 Jansson, Jesper
4 Kortsarz, Guy
4 Li, Jianzhong
4 Marchetti-Spaccamela, Alberto
4 Megow, Nicole
4 Mestre, Julián
4 Miyazawa, Flavio Keidi
4 Nagamochi, Hiroshi
4 Nugent, Michael
4 Parekh, Ojas
4 Pendavingh, Rudi A.
4 Persson, Mia
4 Prädel, Lars
4 Sabharwal, Yogish
4 Stein, Clifford
4 Swamy, Chaitanya
4 Verschae, José
4 Wang, Jianxin
4 Zwart, Bert P.
3 Adamaszek, Anna
3 Adamczyk, Marek
3 Andrews, Matthew T.
3 Angelelli, Enrico
3 Angelopoulos, Spyros
3 Bazzi, Abbas
3 Birks, Martin
3 Buchbinder, Niv
3 Chakaravarthy, Venkatesan T.
3 Chalermsook, Parinya
3 Chekuri, Chandra S.
3 Chen, Enhong
3 Choudhury, Anamitra Roy
3 Chrobak, Marek
3 Ene, Alina
3 Englert, Matthias
3 Fellows, Michael Ralph
3 Figueiredo, Rosa M. V.
3 Frota, Yuri A.
...and 1,102 more Authors
all top 5

Cited in 109 Serials

75 Algorithmica
69 Theoretical Computer Science
31 Mathematical Programming. Series A. Series B
24 SIAM Journal on Computing
24 Journal of Scheduling
22 Operations Research Letters
22 Theory of Computing Systems
22 Journal of Combinatorial Optimization
21 Journal of Computer and System Sciences
19 Discrete Applied Mathematics
19 Information Processing Letters
16 European Journal of Operational Research
14 Mathematics of Operations Research
12 Queueing Systems
11 Journal of Discrete Algorithms
10 Annals of Operations Research
9 Computers & Operations Research
9 Discrete Optimization
7 SIAM Journal on Discrete Mathematics
6 Artificial Intelligence
5 Information and Computation
5 Real-Time Systems
5 International Journal of Foundations of Computer Science
4 Journal of Combinatorial Theory. Series B
4 Operations Research
4 Computer Science Review
3 Discrete Mathematics
3 Combinatorica
3 Computational Geometry
3 Distributed Computing
3 Annals of Mathematics and Artificial Intelligence
3 Data Mining and Knowledge Discovery
3 RAIRO. Operations Research
3 Prikladnaya Diskretnaya Matematika
2 Acta Informatica
2 Advances in Applied Probability
2 Applied Mathematics and Computation
2 European Journal of Combinatorics
2 Discrete & Computational Geometry
2 International Journal of Approximate Reasoning
2 Asia-Pacific Journal of Operational Research
2 Journal of Parallel and Distributed Computing
2 AI Communications
2 Machine Learning
2 Journal of Global Optimization
2 Applied Mathematical Modelling
2 Pattern Recognition
2 Sbornik: Mathematics
2 Constraints
2 International Journal of Applied Mathematics and Computer Science
2 Optimization Letters
2 Algorithms
2 ACM Transactions on Algorithms
2 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Computers & Mathematics with Applications
1 Communications on Pure and Applied Mathematics
1 Israel Journal of Mathematics
1 Physica A
1 The Annals of Probability
1 Information Sciences
1 Journal of Applied Probability
1 Journal of Combinatorial Theory. Series A
1 Journal of Optimization Theory and Applications
1 Kybernetika
1 Mathematika
1 Networks
1 Theory and Decision
1 Transactions of the American Mathematical Society
1 Advances in Applied Mathematics
1 Annals of Pure and Applied Logic
1 Journal of Cryptology
1 Neural Computation
1 International Journal of Computational Geometry & Applications
1 Geometric and Functional Analysis. GAFA
1 Games and Economic Behavior
1 Automation and Remote Control
1 International Journal of Computer Mathematics
1 Expositiones Mathematicae
1 Indagationes Mathematicae. New Series
1 Applicable Algebra in Engineering, Communication and Computing
1 SIAM Journal on Optimization
1 The Australasian Journal of Combinatorics
1 Journal of Mathematical Imaging and Vision
1 Computational Optimization and Applications
1 SIAM Journal on Scientific Computing
1 The Electronic Journal of Combinatorics
1 International Transactions in Operational Research
1 INFORMS Journal on Computing
1 Mathematical Problems in Engineering
1 Journal of Graph Algorithms and Applications
1 Journal of the ACM
1 International Journal of Modern Physics C
1 Foundations of Computational Mathematics
1 Stochastic Models
1 Quantum Information Processing
1 4OR
1 Statistical Methods and Applications
1 Oberwolfach Reports
1 Frontiers of Mathematics in China
1 Electronic Journal of Statistics
...and 9 more Serials

Citations by Year