Nikhil Bansal - RankMe

283 papers A* 82A 13B 17C 4Journal 142Unranked 15

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Expander Decomposition with Almost Optimal Overhead. CoRR Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak
2026	J	`jnl`	Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs. CoRR Nikhil Bansal, Neng Huang, Euiwoong Lee
2025	A*	`conf`	An Improved Bound for the Beck-Fiala Conjecture. FOCS Nikhil Bansal, Haotian Jiang
2025	J	`jnl`	Cornstarch: Distributed Multimodal Training Must Be Multimodality-Aware. CoRR Insu Jang, Runyu Lu, Nikhil Bansal, Ang Chen, Mosharaf Chowdhury
2025	J	`jnl`	Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk. CoRR Nikhil Bansal, Haotian Jiang
2025	J	`jnl`	Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023 Special Issue. ACM Trans. Algorithms Nikhil Bansal, Eun Jung Kim, Viswanath Nagarajan, Aaron Potechin, Lars Rohwedder
2025	A*	`conf`	Optimal 4-Approximation for the Correlated Pandora's Problem. FOCS Nikhil Bansal, Zhiyi Huang, Zixuan Zhu
2025	J	`jnl`	Optimal 4-Approximation for the Correlated Pandora's Problem. CoRR Nikhil Bansal, Zhiyi Huang, Zixuan Zhu
2025	A*	`ed.`	Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025 STOC Michal Koucký, Nikhil Bansal
2025	A*	`conf`	Quasi-Monte Carlo Beyond Hardy-Krause. SODA Nikhil Bansal, Haotian Jiang
2024	A*	`conf`	On Approximating Cutwidth and Pathwidth. FOCS Nikhil Bansal, Dor Katzelnick, Roy Schwartz
2024	J	`jnl`	On a Generalization of Iterated and Randomized Rounding. Theory Comput. Nikhil Bansal
2024	J	`jnl`	Quasi-Monte Carlo Beyond Hardy-Krause. CoRR Nikhil Bansal, Haotian Jiang
2024	A*	`conf`	Reducing Energy Bloat in Large Model Training. SOSP Jae-Won Chung, Yile Gu, Insu Jang, Luoxi Meng, Nikhil Bansal, Mosharaf Chowdhury
2024	A*	`conf`	Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. FOCS Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn
2024	J	`jnl`	Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. CoRR Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn
2023	J	`jnl`	A nearly tight lower bound for the Inf. Process. Lett. Nikhil Bansal, John Kuszmaul, William Kuszmaul
2023	J	`jnl`	Almost Logarithmic Approximation for Cutwidth and Pathwidth. CoRR Nikhil Bansal, Dor Katzelnick, Roy Schwartz
2023	J	`jnl`	Competitive Algorithms for Generalized ACM Trans. Algorithms Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof
2023	J	`jnl`	EATCS Distinguished Dissertation Award for 2022. Bull. EATCS Nikhil Bansal
2023	J	`jnl`	On Min Sum Vertex Cover and Generalized Min Sum Set Cover. SIAM J. Comput. Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali
2023	A	`conf`	On Minimizing Generalized Makespan on Unrelated Machines. APPROX/RANDOM Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
2023	J	`jnl`	On Minimizing Generalized Makespan on Unrelated Machines. CoRR Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
2023	J	`jnl`	Perseus: Removing Energy Bloat from Large Model Training. CoRR Jae-Won Chung, Yile Gu, Insu Jang, Luoxi Meng, Nikhil Bansal, Mosharaf Chowdhury
2023	A*	`ed.`	Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 SODA Nikhil Bansal, Viswanath Nagarajan
2023	A*	`conf`	Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. STOC Nikhil Bansal, Haotian Jiang, Raghu Meka
2023	J	`jnl`	Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture. Random Struct. Algorithms Nikhil Bansal, David G. Harris
2022	J	`jnl`	A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem. CoRR Nikhil Bansal, John Kuszmaul, William Kuszmaul
2022	A	`conf`	A Unified Approach to Discrepancy Minimization. APPROX/RANDOM Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
2022	J	`jnl`	A Unified Approach to Discrepancy Minimization. CoRR Nikhil Bansal, Aditi Laddha, Santosh S. Vempala
2022	A*	`conf`	Balanced Allocations: The Heavily Loaded Case with Deletions. FOCS Nikhil Bansal, William Kuszmaul
2022	J	`jnl`	Balanced Allocations: The Heavily Loaded Case with Deletions. CoRR Nikhil Bansal, William Kuszmaul
2022	J	`jnl`	Flow Time Scheduling and Prefix Beck-Fiala. CoRR Nikhil Bansal, Lars Rohwedder, Ola Svensson
2022	A*	`conf`	Flow time scheduling and prefix Beck-Fiala. STOC Nikhil Bansal, Lars Rohwedder, Ola Svensson
2022	A	`conf`	Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. CCC Nikhil Bansal, Makrand Sinha, Ronald de Wolf
2022	J	`jnl`	Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms. CoRR Nikhil Bansal, Makrand Sinha, Ronald de Wolf
2022	A*	`conf`	Learning-Augmented Weighted Paging. SODA Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee
2022	A	`conf`	Online Metric Allocation and Time-Varying Regularization. ESA Nikhil Bansal, Christian Coester
2022	A	`conf`	Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. ITCS Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2022	J	`jnl`	Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. CoRR Nikhil Bansal, Haotian Jiang, Raghu Meka
2022	A*	`conf`	Smoothed Analysis of the Komlós Conjecture. ICALP Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2022	J	`jnl`	Smoothed Analysis of the Komlós Conjecture. CoRR Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2022	J	`jnl`	Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. ACM Trans. Algorithms Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
2022	A*	`conf`	The power of two choices in graphical allocation. STOC Nikhil Bansal, Ohad N. Feldheim
2021	A*	`ed.`	48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021 ICALP Nikhil Bansal, Emanuela Merelli, James Worrell
2021	B	`conf`	Contention Resolution, Matrix Scaling and Fair Allocation. WAOA Nikhil Bansal, Ilan Reuven Cohen
2021	B	`conf`	Efficient Online Weighted Multi-Level Paging. SPAA Nikhil Bansal, Joseph (Seffi) Naor, Ohad Talmon
2021	A*	`conf`	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. SODA Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali
2021	J	`jnl`	Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines. SIAM J. Comput. Nikhil Bansal, Aravind Srinivasan, Ola Svensson
2021	A*	`conf`	Non-uniform Geometric Set Cover and Scheduling on Multiple Machines. SODA Nikhil Bansal, Jatin Batra
2021	A*	`conf`	Online Discrepancy Minimization for Stochastic Arrivals. SODA Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2021	J	`jnl`	Online metric allocation. CoRR Nikhil Bansal, Christian Coester
2021	J	`jnl`	Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. CoRR Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2021	J	`jnl`	Well-Balanced Allocation on General Graphs. CoRR Nikhil Bansal, Ohad N. Feldheim
2021	A*	`conf`	k-forrelation optimally separates Quantum and classical query complexity. STOC Nikhil Bansal, Makrand Sinha
2020	J	`jnl`	$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity. Electron. Colloquium Comput. Complex. Nikhil Bansal, Makrand Sinha
2020	J	`jnl`	An Asymptotic Lower Bound for Online Vector Bin Packing. CoRR Nikhil Bansal, Ilan Reuven Cohen
2020	J	`jnl`	EATCS Distinguished Dissertation Award 2020 - Call for Nominations. Bull. EATCS Susanne Albers, Nikhil Bansal, Elvira Mayordomo, Dale Miller, Jaroslav Nesetril, Damian Niwinski, David Peleg, Vladimiro Sassone, Alexandra Silva
2020	J	`jnl`	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. CoRR Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali
2020	J	`jnl`	Nested Convex Bodies are Chaseable. Algorithmica Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh
2020	J	`jnl`	On the discrepancy of random low degree set systems. Random Struct. Algorithms Nikhil Bansal, Raghu Meka
2020	J	`jnl`	On-line balancing of random inputs. Random Struct. Algorithms Nikhil Bansal, Joel H. Spencer
2020	J	`jnl`	Online Discrepancy Minimization for Stochastic Arrivals. CoRR Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
2020	A*	`conf`	Online vector balancing and geometric discrepancy. STOC Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
2020	J	`jnl`	Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging. CoRR Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee
2020	J	`jnl`	Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture. CoRR Nikhil Bansal, David G. Harris
2020	A*	`conf`	Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. SODA Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
2020	J	`jnl`	k-Forrelation Optimally Separates Quantum and Classical Query Complexity. CoRR Nikhil Bansal, Makrand Sinha
2019	J	`jnl`	An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. SIAM J. Comput. Nikhil Bansal, Daniel Dadush, Shashwat Garg
2019	J	`jnl`	Geometry of Scheduling on Multiple Machines. CoRR Nikhil Bansal, Jatin Batra
2019	A*	`conf`	New Notions and Constructions of Sparsification for Graphs and Hypergraphs. FOCS Nikhil Bansal, Ola Svensson, Luca Trevisan
2019	J	`jnl`	New Notions and Constructions of Sparsification for Graphs and Hypergraphs. CoRR Nikhil Bansal, Ola Svensson, Luca Trevisan
2019	J	`jnl`	New Tools and Connections for Exponential-Time Approximation. Algorithmica Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
2019	A*	`conf`	On a generalization of iterated and randomized rounding. STOC Nikhil Bansal
2019	A*	`conf`	On the discrepancy of random low degree set systems. SODA Nikhil Bansal, Raghu Meka
2019	J	`jnl`	On-Line Balancing of Random Inputs. CoRR Nikhil Bansal, Joel H. Spencer
2019	J	`jnl`	Online Vector Balancing and Geometric Discrepancy. CoRR Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha
2019	J	`jnl`	Potential-Function Proofs for Gradient Methods. Theory Comput. Nikhil Bansal, Anupam Gupta
2019	J	`jnl`	The ( ACM Trans. Algorithms Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
2019	J	`jnl`	The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. Theory Comput. Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
2018	J	`jnl`	Achievable Performance of Blind Policies in Heavy Traffic. Math. Oper. Res. Nikhil Bansal, Bart Kamphorst, Bert Zwart
2018	A*	`conf`	Competitive Algorithms for Generalized SODA Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof
2018	J	`jnl`	Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems. SIAM J. Comput. Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
2018	A*	`conf`	Nested Convex Bodies are Chaseable. SODA Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh
2018	J	`jnl`	On a generalization of iterated and randomized rounding. CoRR Nikhil Bansal
2018	J	`jnl`	On the Lovász Theta Function for Independent Sets in Sparse Graphs. SIAM J. Comput. Nikhil Bansal, Anupam Gupta, Guru Guruganesh
2018	J	`jnl`	On the discrepancy of random low degree set systems. CoRR Nikhil Bansal, Raghu Meka
2018	B	`conf`	Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems. ISAAC Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, Georg von der Brüggen
2018	J	`jnl`	Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems. CoRR Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, Georg von der Brüggen
2018	J	`jnl`	Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems. CoRR Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh
2018	A*	`conf`	The gram-schmidt walk: a cure for the Banaszczyk blues. STOC Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
2018	J	`jnl`	Tight Bounds for Double Coverage Against Weak Adversaries. Theory Comput. Syst. Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs
2017	A*	`conf`	Algorithmic discrepancy beyond partial coloring. STOC Nikhil Bansal, Shashwat Garg
2017	J	`jnl`	Competitive Algorithms for Generalized k-Server in Uniform Metrics. CoRR Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof
2017	A*	`conf`	Faster space-efficient algorithms for subset sum and k-sum. STOC Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
2017	J	`jnl`	Guest Editors' Foreword. Algorithmica Nikhil Bansal, Irene Finocchi
2017	A*	`conf`	LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. SODA Nikhil Bansal, Daniel Reichman, Seeun William Umboh
2017	J	`jnl`	Nested Convex Bodies are Chaseable. CoRR Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh
2017	J	`jnl`	New Tools and Connections for Exponential-time Approximation. CoRR Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
2017	J	`jnl`	Potential-Function Proofs for First-Order Methods. CoRR Nikhil Bansal, Anupam Gupta
2017	A*	`conf`	The ( SODA Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
2017	J	`jnl`	The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. CoRR Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
2017	J	`jnl`	The local-global conjecture for scheduling with non-linear cost. J. Sched. Nikhil Bansal, Christoph Dürr, Kim Thang Nguyen, Óscar C. Vásquez
2017	J	`jnl`	Tight approximation bounds for dominating set on graphs of bounded arboricity. Inf. Process. Lett. Nikhil Bansal, Seeun William Umboh
2017	A*	`conf`	Weighted k-Server Bounds via Combinatorial Dichotomies. FOCS Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos
2017	J	`jnl`	Weighted k-Server Bounds via Combinatorial Dichotomies. CoRR Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos
2016	J	`jnl`	Algorithmic Discrepancy Beyond Partial Coloring. CoRR Nikhil Bansal, Shashwat Garg
2016	A*	`conf`	An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. FOCS Nikhil Bansal, Daniel Dadush, Shashwat Garg
2016	J	`jnl`	An Algorithm for Komlós Conjecture Matching Banaszczyk's bound. CoRR Nikhil Bansal, Daniel Dadush, Shashwat Garg
2016	J	`jnl`	Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. Algorithmica Nikhil Bansal, Tim Oosterwijk, Tjark Vredeveld, Ruben van der Zwaan
2016	—	`ch.`	Approximation Schemes for Bin Packing. Encyclopedia of Algorithms Nikhil Bansal
2016	B	`conf`	Approximation-Friendly Discrepancy Rounding. IPCO Nikhil Bansal, Viswanath Nagarajan
2016	J	`jnl`	Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems. CoRR Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
2016	J	`jnl`	Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems. CoRR Nikhil Bansal, Shashwat Garg
2016	A*	`conf`	Improved Approximation for Vector Bin Packing. SODA Nikhil Bansal, Marek Eliás, Arindam Khan
2016	A*	`conf`	Lift-and-round to improve weighted completion time on unrelated machines. STOC Nikhil Bansal, Aravind Srinivasan, Ola Svensson
2016	J	`jnl`	Minimizing Maximum Flow-Time on Related Machines. Theory Comput. Nikhil Bansal, Bouke Cloostermans
2016	—	`ch.`	Minimum Flow Time. Encyclopedia of Algorithms Nikhil Bansal
2016	—	`ch.`	Multilevel Feedback Queues. Encyclopedia of Algorithms Nikhil Bansal
2016	J	`jnl`	New Bounds for the $(h, k)$-Server Problem. CoRR Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos
2016	—	`ch.`	Oblivious Routing. Encyclopedia of Algorithms Nikhil Bansal
2016	J	`jnl`	Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs. CoRR Nikhil Bansal, Daniel Reichman, Seeun William Umboh
2016	J	`jnl`	Scheduling (Dagstuhl Seminar 16081). Dagstuhl Reports Nikhil Bansal, Nicole Megow, Clifford Stein
2016	—	`ch.`	Shortest Elapsed Time First Scheduling. Encyclopedia of Algorithms Nikhil Bansal
2016	J	`jnl`	Weighted geometric set multi-cover via quasi-uniform sampling. J. Comput. Geom. Nikhil Bansal, Kirk Pruhs
2015	—	`conf`	A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs. APPROX-RANDOM Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, Clifford Stein
2015	J	`jnl`	A Polylogarithmic-Competitive Algorithm for the J. ACM Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor
2015	J	`jnl`	Achievable Performance of Blind Policies in Heavy Traffic. CoRR Nikhil Bansal, Bart Kamphorst, Bert Zwart
2015	A	`ed.`	Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings ESA Nikhil Bansal, Irene Finocchi
2015	A*	`conf`	Approximating independent sets in sparse graphs. SODA Nikhil Bansal
2015	J	`jnl`	Approximation-Friendly Discrepancy Rounding. CoRR Nikhil Bansal, Viswanath Nagarajan
2015	J	`jnl`	Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines. CoRR Nikhil Bansal, Ola Svensson, Aravind Srinivasan
2015	A*	`conf`	Minimizing Flow-Time on Unrelated Machines. STOC Nikhil Bansal, Janardhan Kulkarni
2015	—	`conf`	Minimizing Maximum Flow-time on Related Machines. APPROX-RANDOM Nikhil Bansal, Bouke Cloostermans
2015	J	`jnl`	Minimum Congestion Mapping in a Cloud. SIAM J. Comput. Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan, Murtaza Zafer
2015	A*	`conf`	On the Lovász Theta function for Independent Sets in Sparse Graphs. STOC Nikhil Bansal, Anupam Gupta, Guru Guruganesh
2015	J	`jnl`	On the Lovász Theta function for Independent Sets in Sparse Graphs. CoRR Nikhil Bansal, Anupam Gupta, Guru Guruganesh
2015	J	`jnl`	On the adaptivity gap of stochastic orienteering. Math. Program. Nikhil Bansal, Viswanath Nagarajan
2015	J	`jnl`	On the number of matroids. Comb. Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol
2015	B	`conf`	Tight Bounds for Double Coverage Against Weak Adversaries. WAOA Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs
2014	J	`jnl`	A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching. Algorithmica Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph Naor
2014	J	`jnl`	A logarithmic approximation for unsplittable flow on line graphs. ACM Trans. Algorithms Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour
2014	J	`jnl`	An entropy argument for counting matroids. J. Comb. Theory B Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol
2014	B	`conf`	Approximating Real-Time Scheduling on Identical Machines. LATIN Nikhil Bansal, Cyriel Rutten, Suzanne van der Ster, Tjark Vredeveld, Ruben van der Zwaan
2014	B	`conf`	Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. LATIN Nikhil Bansal, Tjark Vredeveld, Ruben van der Zwaan
2014	A*	`conf`	Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach. SODA Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li
2014	J	`jnl`	Better Scalable Algorithms for Broadcast Scheduling. ACM Trans. Algorithms Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan
2014	A*	`conf`	Improved Approximation Algorithm for Two-Dimensional Bin Packing. SODA Nikhil Bansal, Arindam Khan
2014	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2014	J	`jnl`	Minimizing Flow-Time on Unrelated Machines. CoRR Nikhil Bansal, Janardhan Kulkarni
2014	—	`conf`	New Developments in Iterated Rounding (Invited Talk). FSTTCS Nikhil Bansal
2014	B	`conf`	On the Adaptivity Gap of Stochastic Orienteering. IPCO Nikhil Bansal, Viswanath Nagarajan
2014	J	`jnl`	The Geometry of Scheduling. SIAM J. Comput. Nikhil Bansal, Kirk Pruhs
2013	J	`jnl`	A Harmonic Algorithm for the 3D Strip Packing Problem. SIAM J. Comput. Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang
2013	J	`jnl`	Deterministic Discrepancy Minimization. Algorithmica Nikhil Bansal, Joel Spencer
2013	J	`jnl`	On generalizations of network design problems with degree bounds. Math. Program. Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, Britta Peis
2013	J	`jnl`	On the Adaptivity Gap of Stochastic Orienteering. CoRR Nikhil Bansal, Viswanath Nagarajan
2013	A*	`conf`	On the number of matroids. SODA Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol
2013	J	`jnl`	Speed Scaling with an Arbitrary Power Function. ACM Trans. Algorithms Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
2012	J	`jnl`	A Primal-Dual Randomized Algorithm for Weighted Paging. J. ACM Nikhil Bansal, Niv Buchbinder, Joseph Naor
2012	J	`jnl`	An entropy argument for counting matroids CoRR Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol
2012	J	`jnl`	Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. Theory Comput. Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, Kirk Pruhs
2012	—	`conf`	Multicast Routing for Energy Minimization Using Speed Scaling. MedAlg Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
2012	J	`jnl`	Randomized Competitive Algorithms for Generalized Caching. SIAM J. Comput. Nikhil Bansal, Niv Buchbinder, Joseph Naor
2012	J	`jnl`	Regularity Lemmas and Combinatorial Algorithms. Theory Comput. Nikhil Bansal, Ryan Williams
2012	J	`jnl`	Semidefinite optimization in discrepancy theory. Math. Program. Nikhil Bansal
2012	J	`jnl`	Solving Packing Integer Programs via Randomized Rounding with Alterations. Theory Comput. Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan
2012	B	`conf`	The Primal-Dual Approach for Online Algorithms. WAOA Nikhil Bansal
2012	A*	`conf`	Tight time-space tradeoff for mutual exclusion. STOC Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally
2012	A	`conf`	Weighted Geometric Set Multi-cover via Quasi-uniform Sampling. ESA Nikhil Bansal, Kirk Pruhs
2012	J	`jnl`	When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra
2011	J	`jnl`	A Polylogarithmic-Competitive Algorithm for the k-Server Problem CoRR Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor
2011	A*	`conf`	A Polylogarithmic-Competitive Algorithm for the k-Server Problem. FOCS Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor
2011	J	`jnl`	Average Rate Speed Scaling. Algorithmica Nikhil Bansal, David P. Bunde, Ho-Leung Chan, Kirk Pruhs
2011	J	`jnl`	Competitive Algorithms for Due Date Scheduling. Algorithmica Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
2011	A	`conf`	Deterministic Discrepancy Minimization. ESA Nikhil Bansal, Joel Spencer
2011	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion CoRR Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	A*	`conf`	Min-max Graph Partitioning and Small Set Expansion. FOCS Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	A*	`conf`	Minimum congestion mapping in a cloud. PODC Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan, Murtaza Zafer
2011	—	`conf`	On Capacitated Set Cover Problems. APPROX-RANDOM Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha
2011	J	`jnl`	Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy. Algorithmica Nikhil Bansal, Danny Z. Chen, Don Coppersmith, Xiaobo Sharon Hu, Shuang Luan, Ewa Misiolek, Baruch Schieber, Chao Wang
2010	A*	`conf`	A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. SODA Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy
2010	—	`conf`	Approximation Algorithms for Diversified Search Ranking. ICALP (2) Nikhil Bansal, Kamal Jain, Anna Kazeykina, Joseph Naor
2010	—	`conf`	Better Scalable Algorithms for Broadcast Scheduling. ICALP (1) Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan
2010	J	`jnl`	Constructive Algorithms for Discrepancy Minimization CoRR Nikhil Bansal
2010	A*	`conf`	Constructive Algorithms for Discrepancy Minimization. FOCS Nikhil Bansal
2010	J	`jnl`	Dynamic pricing for impatient bidders. ACM Trans. Algorithms Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko
2010	—	`conf`	Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. ICALP (1) Nikhil Bansal, Subhash Khot
2010	—	`conf`	Metrical Task Systems and the ICALP (1) Nikhil Bansal, Niv Buchbinder, Joseph Naor
2010	B	`conf`	On IPCO Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan
2010	J	`jnl`	On Generalizations of Network Design Problems with Degree Bounds CoRR Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, Britta Peis
2010	B	`conf`	On Generalizations of Network Design Problems with Degree Bounds. IPCO Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, Britta Peis
2010	J	`jnl`	On the Longest Common Rigid Subsequence Problem. Algorithmica Nikhil Bansal, Moshe Lewenstein, Bin Ma, Kaizhong Zhang
2010	J	`jnl`	Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service. SIAM J. Comput. Nikhil Bansal, Kirk Pruhs
2010	J	`jnl`	The Geometry of Scheduling CoRR Nikhil Bansal, Kirk Pruhs
2010	A*	`conf`	The Geometry of Scheduling. FOCS Nikhil Bansal, Kirk Pruhs
2010	A*	`conf`	Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. SODA Nikhil Bansal, Niv Buchbinder, Joseph Naor
2010	—	`conf`	When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract). ESA (2) Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra
2010	J	`jnl`	When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings CoRR Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra
2009	J	`jnl`	A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing. SIAM J. Comput. Nikhil Bansal, Alberto Caprara, Maxim Sviridenko
2009	B	`conf`	A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability. ISAAC Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, Maxim Sviridenko
2009	A*	`conf`	A logarithmic approximation for unsplittable flow on line graphs. SODA Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour
2009	J	`jnl`	Additive Guarantees for Degree-Bounded Directed Network Design. SIAM J. Comput. Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan
2009	J	`jnl`	Bin-packing with fragile objects and frequency allocation in cellular networks. Wirel. Networks Nikhil Bansal, Zhen Liu, Arvind Sankar
2009	J	`jnl`	Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs. Quantum Inf. Comput. Nikhil Bansal, Sergey Bravyi, Barbara M. Terhal
2009	—	`conf`	Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. ICALP (1) Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, Dmitriy Katz
2009	C	`conf`	Job Admission and Resource Allocation in Distributed Streaming Systems. JSSPP Joel L. Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay S. Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu
2009	J	`jnl`	On k-Column Sparse Packing Programs CoRR Nikhil Bansal, Nitish Korula, Viswanath Nagarajan
2009	A*	`conf`	Optimal Long Code Test with One Free Bit. FOCS Nikhil Bansal, Subhash Khot
2009	A*	`conf`	Regularity Lemmas and Combinatorial Algorithms. FOCS Nikhil Bansal, Ryan Williams
2009	J	`jnl`	Speed Scaling for Weighted Flow Time. SIAM J. Comput. Nikhil Bansal, Kirk Pruhs, Clifford Stein
2009	J	`jnl`	Speed scaling with a solar cell. Theor. Comput. Sci. Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
2009	A*	`conf`	Speed scaling with an arbitrary power function. SODA Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
2009	A*	`conf`	Weighted flow time does not admit O(1)-competitive algorithms. SODA Nikhil Bansal, Ho-Leung Chan
2008	A*	`conf`	Additive guarantees for degree bounded directed network design. STOC Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan
2008	—	`ch.`	Approximation Schemes for Bin Packing. Encyclopedia of Algorithms Nikhil Bansal
2008	B	`conf`	Average Rate Speed Scaling. LATIN Nikhil Bansal, David P. Bunde, Ho-Leung Chan, Kirk Pruhs
2008	J	`jnl`	Improved Approximation Algorithms for Broadcast Scheduling. SIAM J. Comput. Nikhil Bansal, Don Coppersmith, Maxim Sviridenko
2008	—	`ch.`	Minimum Flow Time. Encyclopedia of Algorithms Nikhil Bansal
2008	—	`ch.`	Multi-level Feedback Queues. Encyclopedia of Algorithms Nikhil Bansal
2008	—	`ch.`	Oblivious Routing. Encyclopedia of Algorithms Nikhil Bansal
2008	A*	`conf`	Randomized competitive algorithms for generalized caching. STOC Nikhil Bansal, Niv Buchbinder, Joseph Naor
2008	J	`jnl`	Robust reductions from ranking to classification. Mach. Learn. Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin
2008	A	`conf`	SODA: An Optimizing Scheduler for Large-Scale Stream-Based Distributed Computer Systems. Middleware Joel L. Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay S. Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu, Lisa Fleischer
2008	—	`conf`	Scheduling for Speed Bounded Processors. ICALP (1) Nikhil Bansal, Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee
2008	—	`ch.`	Shortest Elapsed Time First Scheduling. Encyclopedia of Algorithms Nikhil Bansal
2008	C	`conf`	Speed Scaling with a Solar Cell. AAIM Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
2008	A*	`conf`	Towards Optimal Resource Allocation in Partial-Fault Tolerant Applications. INFOCOM Nikhil Bansal, Ranjita Bhagwan, Navendu Jain, Yoonho Park, Deepak S. Turaga, Chitra Venkatramani
2008	C	`conf`	Transport security using mobile technology. ISI P. Panjiyar, P. Mourya, Nikhil Bansal, P. Srivastava, A. Mukherjee
2007	A*	`conf`	A Primal-Dual Randomized Algorithm for Weighted Paging. FOCS Nikhil Bansal, Niv Buchbinder, Joseph Naor
2007	A	`conf`	An ESA Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph Naor
2007	A*	`conf`	Competitive Algorithms for Due Date Scheduling. ICALP Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs
2007	A*	`conf`	Dynamic pricing for impatient bidders. SODA Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko
2007	J	`jnl`	Finding submasses in weighted strings with Fast Fourier Transform. Discret. Appl. Math. Nikhil Bansal, Mark Cieliebak, Zsuzsanna Lipták
2007	A*	`conf`	Harmonic algorithm for 3-dimensional strip packing problem. SODA Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang
2007	J	`jnl`	Minimizing weighted flow time. ACM Trans. Algorithms Nikhil Bansal, Kedar Dhamdhere
2007	A*	`conf`	Non-Preemptive Min-Sum Scheduling with Resource Augmentation. FOCS Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber
2007	A*	`ed.`	Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007 SODA Nikhil Bansal, Kirk Pruhs, Clifford Stein
2007	A*	`conf`	Robust Reductions from Ranking to Classification. COLT Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin
2007	A*	`conf`	Speed scaling for weighted flow time. SODA Nikhil Bansal, Kirk Pruhs, Clifford Stein
2007	J	`jnl`	Speed scaling to manage energy and temperature. J. ACM Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs
2007	J	`jnl`	Two-dimensional bin packing with one-dimensional resource augmentation. Discret. Optim. Nikhil Bansal, Maxim Sviridenko
2006	A*	`conf`	A quasi-PTAS for unsplittable flow on line graphs. STOC Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber
2006	J	`jnl`	Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes. Math. Oper. Res. Nikhil Bansal, José R. Correa, Claire Kenyon, Maxim Sviridenko
2006	J	`jnl`	Handling load with less stress. Queueing Syst. Theory Appl. Nikhil Bansal, David Gamarnik
2006	A*	`conf`	Improved approximation algorithms for broadcast scheduling. SODA Nikhil Bansal, Don Coppersmith, Maxim Sviridenko
2006	A*	`conf`	Improved approximation algorithms for multidimensional bin packing problems. FOCS Nikhil Bansal, Alberto Caprara, Maxim Sviridenko
2006	J	`jnl`	Job Shop Scheduling with Unit Processing Times. Math. Oper. Res. Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko
2006	—	`conf`	Minimizing Setup and Beam-On Times in Radiation Therapy. APPROX-RANDOM Nikhil Bansal, Don Coppersmith, Baruch Schieber
2006	A*	`conf`	The Santa Claus problem. STOC Nikhil Bansal, Maxim Sviridenko
2005	A*	`conf`	A Tale of Two Dimensional Bin Packing. FOCS Nikhil Bansal, Andrea Lodi, Maxim Sviridenko
2005	A*	`conf`	Approximating the average response time in broadcast scheduling. SODA Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor
2005	A*	`conf`	Job shop scheduling with unit processing times. SODA Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko
2005	J	`jnl`	Minimizing Makespan in No-Wait Job Shops. Math. Oper. Res. Nikhil Bansal, Mohammad Mahdian, Maxim Sviridenko
2005	J	`jnl`	Minimizing flow time on a constant number of machines with preemption. Oper. Res. Lett. Nikhil Bansal
2005	J	`jnl`	On the average sojourn time under M/M/1/SRPT. Oper. Res. Lett. Nikhil Bansal
2005	A	`conf`	Speed Scaling to Manage Temperature. STACS Nikhil Bansal, Kirk Pruhs
2004	J	`jnl`	A note on comparing response times in the M/GI/1/FB and M/GI/1/PS queues. Oper. Res. Lett. Adam Wierman, Nikhil Bansal, Mor Harchol-Balter
2004	A*	`conf`	Approximation algorithms for deadline-TSP and vehicle routing with time-windows. STOC Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
2004	J	`jnl`	Correlation Clustering. Mach. Learn. Nikhil Bansal, Avrim Blum, Shuchi Chawla
2004	A*	`conf`	Dynamic Speed Scaling to Manage Energy and Temperature. FOCS Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs
2004	B	`conf`	Efficient Algorithms for Finding Submasses in Weighted Strings. CPM Nikhil Bansal, Mark Cieliebak, Zsuzsanna Lipták
2004	A*	`conf`	Further Improvements in Competitive Guarantees for QoS Buffering. ICALP Nikhil Bansal, Lisa Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko
2004	A*	`conf`	New approximability and inapproximability results for 2-dimensional Bin Packing. SODA Nikhil Bansal, Maxim Sviridenko
2004	J	`jnl`	Non-Clairvoyant Scheduling for Minimizing Mean Slowdown. Algorithmica Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha
2004	A*	`conf`	On minimizing the total flow time on multiple machines. SODA Nikhil Bansal
2004	B	`conf`	Server Scheduling in the Weighted l LATIN Nikhil Bansal, Kirk Pruhs
2003	J	`jnl`	Analysis of the M/G/1 processor-sharing queue with bulk arrivals. Oper. Res. Lett. Nikhil Bansal
2003	A*	`conf`	Capacity, Delay and Mobility in Wireless Ad-Hoc Networks. INFOCOM Nikhil Bansal, Zhen Liu
2003	A*	`conf`	Improving Web Performance in Broadcast-Unicast Networks. INFOCOM Mukesh Agrawal, Amit Manjhi, Nikhil Bansal, Srinivasan Seshan
2003	A*	`conf`	Minimizing weighted flow time. SODA Nikhil Bansal, Kedar Dhamdhere
2003	A	`conf`	Non-clairvoyant Scheduling for Minimizing Mean Slowdown. STACS Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha
2003	J	`jnl`	On the average sojourn time under M/M/1/SRPT. SIGMETRICS Perform. Evaluation Rev. Nikhil Bansal
2003	B	`conf`	Online oblivious routing. SPAA Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson
2003	A	`conf`	Scheduling for Flow-Time with Admission Control. ESA Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere
2003	A*	`conf`	Server scheduling in the L STOC Nikhil Bansal, Kirk Pruhs
2003	J	`jnl`	Size-based scheduling to improve web performance. ACM Trans. Comput. Syst. Mor Harchol-Balter, Bianca Schroeder, Nikhil Bansal, Mukesh Agrawal
2002	—	`conf`	Bin-Packing with Fragile Objects. IFIP TCS Nikhil Bansal, Zhen Liu, Arvind Sankar
2002	A*	`conf`	Correlation Clustering. FOCS Nikhil Bansal, Avrim Blum, Shuchi Chawla
2001	J	`jnl`	Analysis of M/G/1/SRPT under transient overload. SIGMETRICS Perform. Evaluation Rev. Nikhil Bansal, Mor Harchol-Balter
2001	—	`conf`	Analysis of SRPT scheduling: investigating unfairness. SIGMETRICS/Performance Nikhil Bansal, Mor Harchol-Balter
2001	C	`conf`	SRPT Scheduling for Web Servers. JSSPP Mor Harchol-Balter, Nikhil Bansal, Bianca Schroeder, Mukesh Agrawal
1999	B	`conf`	Upper Bounds for MaxSat: Further Improved. ISAAC Nikhil Bansal, Venkatesh Raman