Nikhil Bansal

According to our database, Nikhil Bansal authored at least 185 papers between 1999 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

A nearly tight lower bound for the <i>d</i>-dimensional cow-path problem.

Nikhil Bansal, John Kuszmaul, William Kuszmaul

Inf. Process. Lett., August, 2023

On Min Sum Vertex Cover and Generalized Min Sum Set Cover.

Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali

SIAM J. Comput., April, 2023

Competitive Algorithms for Generalized <i>k</i>-Server in Uniform Metrics.

Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof

ACM Trans. Algorithms, January, 2023

Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture.

Nikhil Bansal, David G. Harris

Random Struct. Algorithms, 2023

EATCS Distinguished Dissertation Award for 2022.

Nikhil Bansal

Bull. EATCS, 2023

Perseus: Removing Energy Bloat from Large Model Training.

Jae-Won Chung, Yile Gu, Insu Jang, Luoxi Meng, Nikhil Bansal, Mosharaf Chowdhury

CoRR, 2023

Almost Logarithmic Approximation for Cutwidth and Pathwidth.

Nikhil Bansal, Dor Katzelnick, Roy Schwartz

CoRR, 2023

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank.

Nikhil Bansal, Haotian Jiang, Raghu Meka

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

On Minimizing Generalized Makespan on Unrelated Machines.

Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu

Proceedings of the Approximation, 2023

2022

Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems.

Sepehr Abbasi Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh

ACM Trans. Algorithms, 2022

A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem.

Nikhil Bansal, John Kuszmaul, William Kuszmaul

CoRR, 2022

Flow time scheduling and prefix Beck-Fiala.

Nikhil Bansal, Lars Rohwedder, Ola Svensson

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

The power of two choices in graphical allocation.

Nikhil Bansal, Ohad N. Feldheim

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Learning-Augmented Weighted Paging.

Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Smoothed Analysis of the Komlós Conjecture.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Balanced Allocations: The Heavily Loaded Case with Deletions.

Nikhil Bansal, William Kuszmaul

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Online Metric Allocation and Time-Varying Regularization.

Nikhil Bansal, Christian Coester

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms.

Nikhil Bansal, Makrand Sinha, Ronald de Wolf

Proceedings of the 37th Computational Complexity Conference, 2022

A Unified Approach to Discrepancy Minimization.

Nikhil Bansal, Aditi Laddha, Santosh S. Vempala

Proceedings of the Approximation, 2022

2021

Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines.

Nikhil Bansal, Aravind Srinivasan, Ola Svensson

SIAM J. Comput., 2021

Online metric allocation.

Nikhil Bansal, Christian Coester

CoRR, 2021

Well-Balanced Allocation on General Graphs.

Nikhil Bansal, Ohad N. Feldheim

CoRR, 2021

Contention Resolution, Matrix Scaling and Fair Allocation.

Nikhil Bansal, Ilan Reuven Cohen

Proceedings of the Approximation and Online Algorithms - 19th International Workshop, 2021

Efficient Online Weighted Multi-Level Paging.

Nikhil Bansal, Joseph (Seffi) Naor, Ohad Talmon

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Online Discrepancy Minimization for Stochastic Arrivals.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover.

Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Non-uniform Geometric Set Cover and Scheduling on Multiple Machines.

Nikhil Bansal, Jatin Batra

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

On-line balancing of random inputs.

Nikhil Bansal, Joel H. Spencer

Random Struct. Algorithms, 2020

On the discrepancy of random low degree set systems.

Nikhil Bansal, Raghu Meka

Random Struct. Algorithms, 2020

$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity.

Nikhil Bansal, Makrand Sinha

Electron. Colloquium Comput. Complex., 2020

EATCS Distinguished Dissertation Award 2020 - Call for Nominations.

Susanne Albers, Nikhil Bansal, Elvira Mayordomo, Dale Miller, Jaroslav Nesetril, Damian Niwinski, David Peleg, Vladimiro Sassone, Alexandra Silva

Bull. EATCS, 2020

Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging.

Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee

CoRR, 2020

An Asymptotic Lower Bound for Online Vector Bin Packing.

Nikhil Bansal, Ilan Reuven Cohen

CoRR, 2020

Nested Convex Bodies are Chaseable.

Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh

Algorithmica, 2020

Online vector balancing and geometric discrepancy.

Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Potential-Function Proofs for Gradient Methods.

Nikhil Bansal, Anupam Gupta

Theory Comput., 2019

The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues.

Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett

Theory Comput., 2019

The (<i>h, k</i>)-Server Problem on Bounded Depth Trees.

Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos

ACM Trans. Algorithms, 2019

An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound.

Nikhil Bansal, Daniel Dadush, Shashwat Garg

SIAM J. Comput., 2019

Geometry of Scheduling on Multiple Machines.

Nikhil Bansal, Jatin Batra

CoRR, 2019

New Tools and Connections for Exponential-Time Approximation.

Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof

Algorithmica, 2019

On a generalization of iterated and randomized rounding.

Nikhil Bansal

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs.

Nikhil Bansal, Ola Svensson, Luca Trevisan

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems.

Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas

SIAM J. Comput., 2018

On the Lovász Theta Function for Independent Sets in Sparse Graphs.

Nikhil Bansal, Anupam Gupta, Guru Guruganesh

SIAM J. Comput., 2018

Tight Bounds for Double Coverage Against Weak Adversaries.

Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos, Kirk Pruhs

Theory Comput. Syst., 2018

Achievable Performance of Blind Policies in Heavy Traffic.

Nikhil Bansal, Bart Kamphorst, Bert Zwart

Math. Oper. Res., 2018

Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems.

Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, Georg von der Brüggen

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017

The local-global conjecture for scheduling with non-linear cost.

Nikhil Bansal, Christoph Dürr, Kim Thang Nguyen, Óscar C. Vásquez

J. Sched., 2017

Tight approximation bounds for dominating set on graphs of bounded arboricity.

Nikhil Bansal, Seeun William Umboh

Inf. Process. Lett., 2017

Potential-Function Proofs for First-Order Methods.

Nikhil Bansal, Anupam Gupta

CoRR, 2017

Competitive Algorithms for Generalized k-Server in Uniform Metrics.

Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos, Jesper Nederlof

CoRR, 2017

Guest Editors' Foreword.

Nikhil Bansal, Irene Finocchi

Algorithmica, 2017

Faster space-efficient algorithms for subset sum and k-sum.

Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Algorithmic discrepancy beyond partial coloring.

Nikhil Bansal, Shashwat Garg

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The (<i>h</i>, <i>k</i>)-Server Problem on Bounded Depth Trees.

Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.

Nikhil Bansal, Daniel Reichman, Seeun William Umboh

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Weighted k-Server Bounds via Combinatorial Dichotomies.

Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Shortest Elapsed Time First Scheduling.

Nikhil Bansal

Encyclopedia of Algorithms, 2016

Oblivious Routing.

Nikhil Bansal

Encyclopedia of Algorithms, 2016

Multilevel Feedback Queues.

Nikhil Bansal

Encyclopedia of Algorithms, 2016

Minimum Flow Time.

Nikhil Bansal

Encyclopedia of Algorithms, 2016

Approximation Schemes for Bin Packing.

Nikhil Bansal

Encyclopedia of Algorithms, 2016

Minimizing Maximum Flow-Time on Related Machines.

Nikhil Bansal, Bouke Cloostermans

Theory Comput., 2016

Weighted geometric set multi-cover via quasi-uniform sampling.

Nikhil Bansal, Kirk Pruhs

J. Comput. Geom., 2016

Scheduling (Dagstuhl Seminar 16081).

Nikhil Bansal, Nicole Megow, Clifford Stein

Dagstuhl Reports, 2016

Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.

Nikhil Bansal, Daniel Reichman, Seeun William Umboh

CoRR, 2016

Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems.

Nikhil Bansal, Shashwat Garg

CoRR, 2016

New Bounds for the $(h, k)$-Server Problem.

Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos

CoRR, 2016

Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.

Nikhil Bansal, Tim Oosterwijk, Tjark Vredeveld, Ruben van der Zwaan

Algorithmica, 2016

Improved Approximation for Vector Bin Packing.

Nikhil Bansal, Marek Eliás, Arindam Khan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Approximation-Friendly Discrepancy Rounding.

Nikhil Bansal, Viswanath Nagarajan

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

2015

Minimum Congestion Mapping in a Cloud.

Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan, Murtaza Zafer

SIAM J. Comput., 2015

On the adaptivity gap of stochastic orienteering.

Nikhil Bansal, Viswanath Nagarajan

Math. Program., 2015

A Polylogarithmic-Competitive Algorithm for the <i>k</i>-Server Problem.

Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor

J. ACM, 2015

On the number of matroids.

Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol

Comb., 2015

Minimizing Flow-Time on Unrelated Machines.

Nikhil Bansal, Janardhan Kulkarni

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximating independent sets in sparse graphs.

Nikhil Bansal

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs.

Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, Clifford Stein

Proceedings of the Approximation, 2015

2014

Better Scalable Algorithms for Broadcast Scheduling.

Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan

ACM Trans. Algorithms, 2014

A logarithmic approximation for unsplittable flow on line graphs.

Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour

ACM Trans. Algorithms, 2014

The Geometry of Scheduling.

Nikhil Bansal, Kirk Pruhs

SIAM J. Comput., 2014

Min-Max Graph Partitioning and Small Set Expansion.

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz

SIAM J. Comput., 2014

An entropy argument for counting matroids.

Nikhil Bansal, Rudi Pendavingh, Jorn G. van der Pol

J. Comb. Theory, Ser. B, 2014

A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching.

Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph Naor

Algorithmica, 2014

Improved Approximation Algorithm for Two-Dimensional Bin Packing.

Nikhil Bansal, Arindam Khan

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach.

Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.

Nikhil Bansal, Tjark Vredeveld, Ruben van der Zwaan

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Approximating Real-Time Scheduling on Identical Machines.

Nikhil Bansal, Cyriel Rutten, Suzanne van der Ster, Tjark Vredeveld, Ruben van der Zwaan

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

New Developments in Iterated Rounding (Invited Talk).

Nikhil Bansal

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

2013

Speed Scaling with an Arbitrary Power Function.

Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs

ACM Trans. Algorithms, 2013

A Harmonic Algorithm for the 3D Strip Packing Problem.

Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang

SIAM J. Comput., 2013

On generalizations of network design problems with degree bounds.

Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, Britta Peis

Math. Program., 2013

Deterministic Discrepancy Minimization.

Nikhil Bansal, Joel Spencer

Algorithmica, 2013

2012

Regularity Lemmas and Combinatorial Algorithms.

Nikhil Bansal, Ryan Williams

Theory Comput., 2012

Solving Packing Integer Programs via Randomized Rounding with Alterations.

Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan

Theory Comput., 2012

Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule.

Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, Kirk Pruhs

Theory Comput., 2012

Randomized Competitive Algorithms for Generalized Caching.

Nikhil Bansal, Niv Buchbinder, Joseph Naor

SIAM J. Comput., 2012

Semidefinite optimization in discrepancy theory.

Nikhil Bansal

Math. Program., 2012

A Primal-Dual Randomized Algorithm for Weighted Paging.

Nikhil Bansal, Niv Buchbinder, Joseph Naor

J. ACM, 2012

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings.

Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra

Algorithmica, 2012

The Primal-Dual Approach for Online Algorithms.

Nikhil Bansal

Proceedings of the Approximation and Online Algorithms - 10th International Workshop, 2012

Tight time-space tradeoff for mutual exclusion.

Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Multicast Routing for Energy Minimization Using Speed Scaling.

Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein

Proceedings of the Design and Analysis of Algorithms, 2012

2011

Competitive Algorithms for Due Date Scheduling.

Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs

Algorithmica, 2011

Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy.

Nikhil Bansal, Danny Z. Chen, Don Coppersmith, Xiaobo Sharon Hu, Shuang Luan, Ewa Misiolek, Baruch Schieber, Chao Wang

Algorithmica, 2011

Average Rate Speed Scaling.

Nikhil Bansal, David P. Bunde, Ho-Leung Chan, Kirk Pruhs

Algorithmica, 2011

A Polylogarithmic-Competitive Algorithm for the k-Server Problem.

Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On Capacitated Set Cover Problems.

Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Dynamic pricing for impatient bidders.

Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko

ACM Trans. Algorithms, 2010

Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service.

Nikhil Bansal, Kirk Pruhs

SIAM J. Comput., 2010

On the Longest Common Rigid Subsequence Problem.

Nikhil Bansal, Moshe Lewenstein, Bin Ma, Kaizhong Zhang

Algorithmica, 2010

A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover.

Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Towards the Randomized k-Server Conjecture: A Primal-Dual Approach.

Nikhil Bansal, Niv Buchbinder, Joseph Naor

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On <i>k</i>-Column Sparse Packing Programs.

Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.

Nikhil Bansal, Subhash Khot

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Approximation Algorithms for Diversified Search Ranking.

Nikhil Bansal, Kamal Jain, Anna Kazeykina, Joseph Naor

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Metrical Task Systems and the <i>k</i>-Server Problem on HSTs.

Nikhil Bansal, Niv Buchbinder, Joseph Naor

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Constructive Algorithms for Discrepancy Minimization.

Nikhil Bansal

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract).

Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra

Proceedings of the Algorithms, 2010

2009

Bin-packing with fragile objects and frequency allocation in cellular networks.

Nikhil Bansal, Zhen Liu, Arvind Sankar

Wirel. Networks, 2009

Speed scaling with a solar cell.

Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs

Theor. Comput. Sci., 2009

Speed Scaling for Weighted Flow Time.

Nikhil Bansal, Kirk Pruhs, Clifford Stein

SIAM J. Comput., 2009

Additive Guarantees for Degree-Bounded Directed Network Design.

Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan

SIAM J. Comput., 2009

A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing.

Nikhil Bansal, Alberto Caprara, Maxim Sviridenko

SIAM J. Comput., 2009

Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs.

Nikhil Bansal, Sergey Bravyi, Barbara M. Terhal

Quantum Inf. Comput., 2009

On k-Column Sparse Packing Programs

Nikhil Bansal, Nitish Korula, Viswanath Nagarajan

CoRR, 2009

Weighted flow time does not admit O(1)-competitive algorithms.

Nikhil Bansal, Ho-Leung Chan

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Job Admission and Resource Allocation in Distributed Streaming Systems.

Joel L. Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay S. Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu

Proceedings of the Job Scheduling Strategies for Parallel Processing, 2009

A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability.

Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, Maxim Sviridenko

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Optimal Long Code Test with One Free Bit.

Nikhil Bansal, Subhash Khot

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Shortest Elapsed Time First Scheduling.

Nikhil Bansal

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Oblivious Routing.

Nikhil Bansal

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Multi-level Feedback Queues.

Nikhil Bansal

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Minimum Flow Time.

Nikhil Bansal

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Approximation Schemes for Bin Packing.

Nikhil Bansal

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Improved Approximation Algorithms for Broadcast Scheduling.

Nikhil Bansal, Don Coppersmith, Maxim Sviridenko

SIAM J. Comput., 2008

Robust reductions from ranking to classification.

Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin

Mach. Learn., 2008

SODA: An Optimizing Scheduler for Large-Scale Stream-Based Distributed Computer Systems.

Joel L. Wolf, Nikhil Bansal, Kirsten Hildrum, Sujay S. Parekh, Deepak Rajan, Rohit Wagle, Kun-Lung Wu, Lisa Fleischer

Proceedings of the Middleware 2008, 2008

Transport security using mobile technology.

P. Panjiyar, P. Mourya, Nikhil Bansal, P. Srivastava, A. Mukherjee

Proceedings of the IEEE International Conference on Intelligence and Security Informatics, 2008

Towards Optimal Resource Allocation in Partial-Fault Tolerant Applications.

Nikhil Bansal, Ranjita Bhagwan, Navendu Jain, Yoonho Park, Deepak S. Turaga, Chitra Venkatramani

Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

Scheduling for Speed Bounded Processors.

Nikhil Bansal, Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Minimizing weighted flow time.

Nikhil Bansal, Kedar Dhamdhere

ACM Trans. Algorithms, 2007

Speed scaling to manage energy and temperature.

Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs

J. ACM, 2007

Two-dimensional bin packing with one-dimensional resource augmentation.

Nikhil Bansal, Maxim Sviridenko

Discret. Optim., 2007

Finding submasses in weighted strings with Fast Fourier Transform.

Nikhil Bansal, Mark Cieliebak, Zsuzsanna Lipták

Discret. Appl. Math., 2007

Harmonic algorithm for 3-dimensional strip packing problem.

Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Non-Preemptive Min-Sum Scheduling with Resource Augmentation.

Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

An <i>O</i> (log² <i>k</i> )-Competitive Algorithm for Metric Bipartite Matching.

Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph Naor

Proceedings of the Algorithms, 2007

2006

Handling load with less stress.

Nikhil Bansal, David Gamarnik

Queueing Syst. Theory Appl., 2006

Job Shop Scheduling with Unit Processing Times.

Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko

Math. Oper. Res., 2006

Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes.

Nikhil Bansal, José R. Correa, Claire Kenyon, Maxim Sviridenko

Math. Oper. Res., 2006

The Santa Claus problem.

Nikhil Bansal, Maxim Sviridenko

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

A quasi-PTAS for unsplittable flow on line graphs.

Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Improved approximation algorithms for multidimensional bin packing problems.

Nikhil Bansal, Alberto Caprara, Maxim Sviridenko

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Minimizing Setup and Beam-On Times in Radiation Therapy.

Nikhil Bansal, Don Coppersmith, Baruch Schieber

Proceedings of the Approximation, 2006

2005

Minimizing flow time on a constant number of machines with preemption.

Nikhil Bansal

Oper. Res. Lett., 2005

Minimizing Makespan in No-Wait Job Shops.

Nikhil Bansal, Mohammad Mahdian, Maxim Sviridenko

Math. Oper. Res., 2005

Speed Scaling to Manage Temperature.

Nikhil Bansal, Kirk Pruhs

Proceedings of the STACS 2005, 2005

Approximating the average response time in broadcast scheduling.

Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

A Tale of Two Dimensional Bin Packing.

Nikhil Bansal, Andrea Lodi, Maxim Sviridenko

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

A note on comparing response times in the M/GI/1/FB and M/GI/1/PS queues.

Adam Wierman, Nikhil Bansal, Mor Harchol-Balter

Oper. Res. Lett., 2004

Correlation Clustering.

Nikhil Bansal, Avrim Blum, Shuchi Chawla

Mach. Learn., 2004

Non-Clairvoyant Scheduling for Minimizing Mean Slowdown.

Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha

Algorithmica, 2004

Approximation algorithms for deadline-TSP and vehicle routing with time-windows.

Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

New approximability and inapproximability results for 2-dimensional Bin Packing.

Nikhil Bansal, Maxim Sviridenko

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

On minimizing the total flow time on multiple machines.

Nikhil Bansal

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Server Scheduling in the Weighted l_p Norm.

Nikhil Bansal, Kirk Pruhs

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Further Improvements in Competitive Guarantees for QoS Buffering.

Nikhil Bansal, Lisa Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Dynamic Speed Scaling to Manage Energy and Temperature.

Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Efficient Algorithms for Finding Submasses in Weighted Strings.

Nikhil Bansal, Mark Cieliebak, Zsuzsanna Lipták

Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

2003

Size-based scheduling to improve web performance.

Mor Harchol-Balter, Bianca Schroeder, Nikhil Bansal, Mukesh Agrawal

ACM Trans. Comput. Syst., 2003

On the average sojourn time under M/M/1/SRPT.

Nikhil Bansal

SIGMETRICS Perform. Evaluation Rev., 2003

Analysis of the M/G/1 processor-sharing queue with bulk arrivals.

Nikhil Bansal

Oper. Res. Lett., 2003

Server scheduling in the L_p norm: a rising tide lifts all boat.

Nikhil Bansal, Kirk Pruhs

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Online oblivious routing.

Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Capacity, Delay and Mobility in Wireless Ad-Hoc Networks.

Nikhil Bansal, Zhen Liu

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

Improving Web Performance in Broadcast-Unicast Networks.

Mukesh Agrawal, Amit Manjhi, Nikhil Bansal, Srinivasan Seshan

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

Scheduling for Flow-Time with Admission Control.

Nikhil Bansal, Avrim Blum, Shuchi Chawla, Kedar Dhamdhere

Proceedings of the Algorithms, 2003

2002

Bin-Packing with Fragile Objects.

Nikhil Bansal, Zhen Liu, Arvind Sankar

Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

2001

Analysis of M/G/1/SRPT under transient overload.

Nikhil Bansal, Mor Harchol-Balter

SIGMETRICS Perform. Evaluation Rev., 2001

Analysis of SRPT scheduling: investigating unfairness.

Nikhil Bansal, Mor Harchol-Balter

Proceedings of the Joint International Conference on Measurements and Modeling of Computer Systems, 2001

SRPT Scheduling for Web Servers.

Mor Harchol-Balter, Nikhil Bansal, Bianca Schroeder, Mukesh Agrawal

Proceedings of the Job Scheduling Strategies for Parallel Processing, 2001

1999

Upper Bounds for MaxSat: Further Improved.

Nikhil Bansal, Venkatesh Raman

Proceedings of the Algorithms and Computation, 10th International Symposium, 1999