☰

Nikhil Bansal, Ph.D. - Publications

Affiliations: 
2003 Carnegie Mellon University, Pittsburgh, PA 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

58 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Bansal N, Böhm M, Eliáš M, Koumoutsos G, Umboh SW. Nested Convex Bodies are Chaseable Algorithmica. 82: 1640-1653. DOI: 10.1007/S00453-019-00661-X  0.333
2020 Bansal N, Spencer JH. On-Line Balancing of Random Inputs Random Structures and Algorithms. DOI: 10.1002/Rsa.20955  0.333
2019 Bansal N, Chalermsook P, Laekhanukit B, Nanongkai D, Nederlof J. New Tools and Connections for Exponential-Time Approximation. Algorithmica. 81: 3993-4009. PMID 31496549 DOI: 10.1007/S00453-018-0512-8  0.462
2019 Bansal N, Dadush D, Garg S, Lovett S. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues Theory of Computing. 15: 1-27. DOI: 10.4086/Toc.2019.V015A021  0.378
2019 Bansal N, Dadush D, Garg S. An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound Siam Journal On Computing. 48: 534-553. DOI: 10.1137/17M1126795  0.4
2018 Bansal N, Garg S, Nederlof J, Vyas N. Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems Siam Journal On Computing. 47: 1755-1777. DOI: 10.1137/17M1158203  0.431
2018 Bansal N, Gupta A, Guruganesh G. On the Lovász Theta Function for Independent Sets in Sparse Graphs Siam Journal On Computing. 47: 1039-1055. DOI: 10.1137/15M1051002  0.348
2017 Bansal N, Umboh SW. Tight approximation bounds for dominating set on graphs of bounded arboricity Information Processing Letters. 122: 21-24. DOI: 10.1016/J.Ipl.2017.01.011  0.375
2016 Bansal N, Oosterwijk T, Vredeveld T, van der Zwaan R. Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. Algorithmica. 76: 1077-1096. PMID 32355383 DOI: 10.1007/S00453-016-0116-0  0.45
2016 Bansal N, Srinivasan A, Svensson O. Lift-and-round to improve weighted completion time on unrelated machines Proceedings of the Annual Acm Symposium On Theory of Computing. 19: 156-167. DOI: 10.1137/16M1099583  0.42
2016 Bansal N, Dürr C, Thang NK, Vásquez ÓC. The local–global conjecture for scheduling with non-linear cost Journal of Scheduling. 1-16. DOI: 10.1007/S10951-015-0466-5  0.419
2015 Bansal N, Buchbinder N, Madry A, Naor JS. A polylogarithmic-competitive algorithm for the k-server problem Journal of the Acm. 62. DOI: 10.1145/2783434  0.427
2015 Bansal N, Lee KW, Nagarajan V, Zafer M. Minimum congestion mapping in a cloud Siam Journal On Computing. 44: 819-843. DOI: 10.1137/110845239  0.389
2015 Bansal N, Nagarajan V. On the adaptivity gap of stochastic orienteering Mathematical Programming. DOI: 10.1007/S10107-015-0927-9  0.37
2014 Bansal N, Krishnaswamy R, Nagarajan V. Better scalable algorithms for broadcast scheduling Acm Transactions On Algorithms. 11. DOI: 10.1145/2636916  0.45
2014 Bansal N, Friggstad Z, Khandekar R, Salavatipour MR. A logarithmic approximation for unsplittable flow on line graphs Acm Transactions On Algorithms. 10. DOI: 10.1145/2532645  0.441
2014 Bansal N, Buchbinder N, Gupta A, Naor J(. A randomized O ( log^2 k )-competitive algorithm for metric bipartite matching Algorithmica. 68: 390-403. DOI: 10.1007/S00453-012-9676-9  0.383
2014 Bansal N. Algorithmic aspects of combinatorial discrepancy Lecture Notes in Mathematics. 2107: 425-457. DOI: 10.1007/978-3-319-04696-9_6  0.425
2013 Bansal N, Chan HL, Pruhs K. Speed scaling with an arbitrary power function Acm Transactions On Algorithms. 9. DOI: 10.1145/2438645.2438650  0.405
2013 Bansal N, Han X, Iwama K, Sviridenko M, Zhang G. A Harmonic Algorithm for the 3D Strip Packing Problem Siam Journal On Computing. 42: 579-592. DOI: 10.1137/070691607  0.371
2013 Bansal N, Khandekar R, Könemann J, Nagarajan V, Peis B. On generalizations of network design problems with degree bounds Mathematical Programming. 141: 479-506. DOI: 10.1007/S10107-012-0537-8  0.456
2013 Bansal N, Spencer J. Deterministic discrepancy minimization Algorithmica. 67: 451-471. DOI: 10.1007/S00453-012-9728-1  0.394
2012 Bansal N, Korula N, Nagarajan V, Srinivasan A. Theory of Computing. 8: 533-565. DOI: 10.4086/Toc.2012.V008A024  0.401
2012 Bansal N, Pruhs K. Weighted geometric set multi-cover via quasi-uniform sampling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7501: 145-156. DOI: 10.20382/Jocg.V7I1A11  0.328
2012 Bansal N, Buchbinder N, Naor J(. A Primal-Dual Randomized Algorithm for Weighted Paging Journal of the Acm. 59: 19. DOI: 10.1145/2339123.2339126  0.437
2012 Bansal N, Buchbinder N, Naor J(. Randomized Competitive Algorithms for Generalized Caching Siam Journal On Computing. 41: 391-414. DOI: 10.1137/090779000  0.436
2012 Bansal N. Semidefinite optimization in discrepancy theory Mathematical Programming. 134: 5-22. DOI: 10.1007/S10107-012-0546-7  0.389
2011 Bansal N, Feige U, Krauthgamer R, Makarychev K, Nagarajan V, Naor J, Schwartz R. Min-max graph partitioning and small set expansion Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 17-26. DOI: 10.1137/120873996  0.46
2011 Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings Algorithmica (New York). 1-30. DOI: 10.1007/S00453-011-9511-8  0.39
2010 Bansal N, Pruhs K. The geometry of scheduling Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 407-414. DOI: 10.1137/130911317  0.392
2010 Bansal N, Pruhs KR. Server scheduling to balance priorities, fairness, and average quality of service Siam Journal On Computing. 39: 3311-3335. DOI: 10.1137/090772228  0.407
2010 Bansal N. Constructive algorithms for discrepancy minimization Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 3-10. DOI: 10.1109/FOCS.2010.7  0.316
2010 Bansal N, Lewenstein M, Ma B, Zhang K. On the Longest Common Rigid Subsequence Problem Algorithmica. 56: 270-280. DOI: 10.1007/S00453-008-9175-1  0.404
2010 Bansal N, Gupta A, Krishnaswamy R. A constant factor approximation algorithm for generalized min-sum set cover Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1539-1545.  0.327
2009 Bansal N, Chan HL, Pruhs K, Katz D. Improved bounds for speed scaling in devices obeying the cube-root rule Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5555: 144-155. DOI: 10.4086/Toc.2012.V008A009  0.38
2009 Bansal N, Williams R. Regularity lemmas and combinatorial algorithms Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 745-754. DOI: 10.4086/Toc.2012.V008A004  0.407
2009 Bansal N, Caprara A, Sviridenko M. A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing Siam Journal On Computing. 39: 1256-1278. DOI: 10.1137/080736831  0.442
2009 Bansal N, Khandekar R, Nagarajan V. Additive Guarantees for Degree-Bounded Directed Network Design Siam Journal On Computing. 39: 1413-1431. DOI: 10.1137/080734340  0.419
2009 Bansal N, Liu Z, Sankar A. Bin-packing with fragile objects and frequency allocation in cellular networks Wireless Networks. 15: 821-830. DOI: 10.1007/S11276-007-0081-2  0.419
2009 Bansal N, Chen DZ, Coppersmith D, Hu XS, Luan S, Misiołek E, Schieber B, Wang C. Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy Algorithmica. 60: 421-450. DOI: 10.1007/S00453-009-9354-8  0.436
2009 Bansal N, Chan HL. Weighted flow time does not admit O(1)-competitive algorithms Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1238-1244.  0.392
2008 Bansal N, Coppersmith D, Sviridenko M. Improved Approximation Algorithms for Broadcast Scheduling Siam Journal On Computing. 38: 1157-1174. DOI: 10.1137/060674417  0.473
2008 Balcan MF, Bansal N, Beygelzimer A, Coppersmith D, Langford J, Sorkin GB. Robust reductions from ranking to classification Machine Learning. 72: 139-153. DOI: 10.1007/S10994-008-5058-6  0.544
2008 Bansal N, Bunde DP, Chan HL, Pruhs K. Average rate speed scaling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4957: 240-251. DOI: 10.1007/S00453-009-9379-Z  0.307
2007 Bansal N, Kimbrel T, Pruhs K. Speed scaling to manage energy and temperature Journal of the Acm. 54. DOI: 10.1145/1206035.1206038  0.352
2007 Bansal N, Pruhs K, Stein C. Speed scaling for weighted flow time Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 7: 805-813. DOI: 10.1137/08072125X  0.372
2007 Bansal N, Sviridenko M. Two-dimensional bin packing with one-dimensional resource augmentation Discrete Optimization. 4: 143-153. DOI: 10.1016/J.Disopt.2006.09.001  0.413
2007 Bansal N, Cieliebak M, Lipták Z. Finding submasses in weighted strings with Fast Fourier Transform Discrete Applied Mathematics. 155: 707-718. DOI: 10.1016/J.Dam.2005.09.019  0.396
2007 Bansal N, Chan HL, Pruhs K. Competitive algorithms for due date scheduling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4596: 28-39. DOI: 10.1007/S00453-009-9321-4  0.455
2006 Bansal N, Kimbrel T, Sviridenko M. Job Shop Scheduling with Unit Processing Times Mathematics of Operations Research. 31: 381-389. DOI: 10.1287/Moor.1060.0189  0.425
2006 Bansal N, Correa JR, Kenyon C, Sviridenko M. Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes Mathematics of Operations Research. 31: 31-49. DOI: 10.1287/Moor.1050.0168  0.388
2006 Bansal N, Gamarnik D. Handling load with less stress Queueing Systems. 54: 45-54. DOI: 10.1007/S11134-006-8218-Z  0.303
2005 Bansal N, Mahdian M, Sviridenko M. Minimizing Makespan in No-Wait Job Shops Mathematics of Operations Research. 30: 817-831. DOI: 10.1287/Moor.1050.0155  0.386
2005 Bansal N. Minimizing flow time on a constant number of machines with preemption Operations Research Letters. 33: 267-273. DOI: 10.1016/J.Orl.2004.07.008  0.376
2004 Bansal N, Dhamdhere K, Sinha A. Non-Clairvoyant Scheduling for Minimizing Mean Slowdown Algorithmica. 40: 305-318. DOI: 10.1007/S00453-004-1115-0  0.44
2003 Harchol-Balter M, Schroeder B, Bansal N, Agrawal M. Size-based scheduling to improve web performance Acm Transactions On Computer Systems. 21: 207-233. DOI: 10.1145/762483.762486  0.323
2003 Bansal N, Dhamdhere K. Minimizing weighted flow time Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 508-516. DOI: 10.1145/1290672.1290676  0.45
2003 Bansal N. Analysis of the M/G/1 processor-sharing queue with bulk arrivals Operations Research Letters. 31: 401-405. DOI: 10.1016/S0167-6377(03)00029-4  0.301
Show low-probability matches.