# Nikhil Bansal

According to our database

Collaborative distances:

^{1}, Nikhil Bansal authored at least 150 papers between 1999 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2019

The (

*h, k*)-Server Problem on Bounded Depth Trees.
ACM Trans. Algorithms, 2019

On a generalization of iterated and randomized rounding.

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

On the discrepancy of random low degree set systems.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

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

SIAM J. Comput., 2018

Achievable Performance of Blind Policies in Heavy Traffic.

Math. Oper. Res., 2018

The gram-schmidt walk: a cure for the Banaszczyk blues.

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Nested Convex Bodies are Chaseable.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Competitive Algorithms for Generalized

*k*-Server in Uniform Metrics.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems.

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

2017

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

J. Scheduling, 2017

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

Inf. Process. Lett., 2017

Guest Editors' Foreword.

Algorithmica, 2017

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

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

Algorithmic discrepancy beyond partial coloring.

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

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.

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

Weighted k-Server Bounds via Combinatorial Dichotomies.

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

2016

Shortest Elapsed Time First Scheduling.

Encyclopedia of Algorithms, 2016

Oblivious Routing.

Encyclopedia of Algorithms, 2016

Multilevel Feedback Queues.

Encyclopedia of Algorithms, 2016

Minimum Flow Time.

Encyclopedia of Algorithms, 2016

Approximation Schemes for Bin Packing.

Encyclopedia of Algorithms, 2016

Scheduling (Dagstuhl Seminar 16081).

Dagstuhl Reports, 2016

Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.

Algorithmica, 2016

Lift-and-round to improve weighted completion time on unrelated machines.

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Improved Approximation for Vector Bin Packing.

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

Approximation-Friendly Discrepancy Rounding.

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

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

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

A Polylogarithmic-Competitive Algorithm for the

*k*-Server Problem.
J. ACM, 2015

Tight Bounds for Double Coverage Against Weak Adversaries.

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

Minimizing Flow-Time on Unrelated Machines.

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

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

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

Approximating independent sets in sparse graphs.

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

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

Proceedings of the Approximation, 2015

Minimizing Maximum Flow-time on Related Machines.

Proceedings of the Approximation, 2015

2014

An entropy argument for counting matroids.

J. Comb. Theory, Ser. B, 2014

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

Algorithmica, 2014

Improved Approximation Algorithm for Two-Dimensional Bin Packing.

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

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

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

Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.

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

Approximating Real-Time Scheduling on Identical Machines.

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

On the Adaptivity Gap of Stochastic Orienteering.

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

New Developments in Iterated Rounding (Invited Talk).

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

2013

A Harmonic Algorithm for the 3D Strip Packing Problem.

SIAM J. Comput., 2013

On the number of matroids.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Solving Packing Integer Programs via Randomized Rounding with Alterations.

Theory of Computing, 2012

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

Theory of Computing, 2012

Semidefinite optimization in discrepancy theory.

Math. Program., 2012

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

Algorithmica, 2012

The Primal-Dual Approach for Online Algorithms.

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

Tight time-space tradeoff for mutual exclusion.

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

Multicast Routing for Energy Minimization Using Speed Scaling.

Proceedings of the Design and Analysis of Algorithms, 2012

Weighted Geometric Set Multi-cover via Quasi-uniform Sampling.

Proceedings of the Algorithms - ESA 2012, 2012

2011

Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy.

Algorithmica, 2011

Minimum congestion mapping in a cloud.

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Min-max Graph Partitioning and Small Set Expansion.

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

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

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

Deterministic Discrepancy Minimization.

Proceedings of the Algorithms - ESA 2011, 2011

On Capacitated Set Cover Problems.

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

2010

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

SIAM J. Comput., 2010

On the Longest Common Rigid Subsequence Problem.

Algorithmica, 2010

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

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

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

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

On

*k*-Column Sparse Packing Programs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010

On Generalizations of Network Design Problems with Degree Bounds.

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

Better Scalable Algorithms for Broadcast Scheduling.

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

Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.

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

Approximation Algorithms for Diversified Search Ranking.

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

Metrical Task Systems and the

*k*-Server Problem on HSTs.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

The Geometry of Scheduling.

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

Constructive Algorithms for Discrepancy Minimization.

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).

Proceedings of the Algorithms, 2010

2009

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

Wireless Networks, 2009

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

SIAM J. Comput., 2009

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

Quantum Information & Computation, 2009

A logarithmic approximation for unsplittable flow on line graphs.

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

Speed scaling with an arbitrary power function.

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

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

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

Job Admission and Resource Allocation in Distributed Streaming Systems.

Proceedings of the Job Scheduling Strategies for Parallel Processing, 2009

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

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

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

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Regularity Lemmas and Combinatorial Algorithms.

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

Optimal Long Code Test with One Free Bit.

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

2008

Shortest Elapsed Time First Scheduling.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Oblivious Routing.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Multi-level Feedback Queues.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Minimum Flow Time.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Approximation Schemes for Bin Packing.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Additive guarantees for degree bounded directed network design.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Randomized competitive algorithms for generalized caching.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

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

Proceedings of the Middleware 2008, 2008

Average Rate Speed Scaling.

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Transport security using mobile technology.

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

Towards Optimal Resource Allocation in Partial-Fault Tolerant Applications.

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

Scheduling for Speed Bounded Processors.

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

Speed Scaling with a Solar Cell.

Proceedings of the Algorithmic Aspects in Information and Management, 2008

2007

Speed scaling to manage energy and temperature.

J. ACM, 2007

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

Discrete Optimization, 2007

Finding submasses in weighted strings with Fast Fourier Transform.

Discrete Applied Mathematics, 2007

Automatic Power Modeling of Infrastructure IP for System-on-Chip Power Analysis.

Proceedings of the 20th International Conference on VLSI Design (VLSI Design 2007), 2007

Speed scaling for weighted flow time.

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

Harmonic algorithm for 3-dimensional strip packing problem.

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

Dynamic pricing for impatient bidders.

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

Competitive Algorithms for Due Date Scheduling.

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Non-Preemptive Min-Sum Scheduling with Resource Augmentation.

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

A Primal-Dual Randomized Algorithm for Weighted Paging.

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

Proceedings of the Algorithms, 2007

Robust Reductions from Ranking to Classification.

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

Handling load with less stress.

Queueing Syst., 2006

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

Math. Oper. Res., 2006

The Santa Claus problem.

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

A quasi-PTAS for unsplittable flow on line graphs.

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

Improved approximation algorithms for broadcast scheduling.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved approximation algorithms for multidimensional bin packing problems.

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

Minimizing Setup and Beam-On Times in Radiation Therapy.

Proceedings of the Approximation, 2006

2005

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

Oper. Res. Lett., 2005

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

Oper. Res. Lett., 2005

Minimizing Makespan in No-Wait Job Shops.

Math. Oper. Res., 2005

Power Monitors: A Framework for System-Level Power Estimation Using Heterogeneous Power Models.

Proceedings of the 18th International Conference on VLSI Design (VLSI Design 2005), 2005

Speed Scaling to Manage Temperature.

Proceedings of the STACS 2005, 2005

Job shop scheduling with unit processing times.

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

Approximating the average response time in broadcast scheduling.

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

A Tale of Two Dimensional Bin Packing.

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.

Oper. Res. Lett., 2004

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

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

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

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

On minimizing the total flow time on multiple machines.

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

Server Scheduling in the Weighted l

_{p}Norm.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Further Improvements in Competitive Guarantees for QoS Buffering.

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

Interconnect-Aware Mapping of Applications to Coarse-Grain Reconfigurable Architectures.

Proceedings of the Field Programmable Logic and Application, 2004

Dynamic Speed Scaling to Manage Energy and Temperature.

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

Network Topology Exploration of Mesh-Based Coarse-Grain Reconfigurable Architectures.

Proceedings of the 2004 Design, 2004

Efficient Algorithms for Finding Submasses in Weighted Strings.

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

2003

Size-based scheduling to improve web performance.

ACM Trans. Comput. Syst., 2003

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

SIGMETRICS Performance Evaluation Review, 2003

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

Oper. Res. Lett., 2003

Server scheduling in the L

_{p}norm: a rising tide lifts all boat.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Non-clairvoyant Scheduling for Minimizing Mean Slowdown.

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Online oblivious routing.

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

Minimizing weighted flow time.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

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

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.

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.

Proceedings of the Algorithms, 2003

An efficient retargetable framework for instruction-set simulation.

Proceedings of the 1st IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, 2003

2002

Bin-Packing with Fragile Objects.

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

Correlation Clustering.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

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

SIGMETRICS Performance Evaluation Review, 2001

Analysis of SRPT scheduling: investigating unfairness.

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

SRPT Scheduling for Web Servers.

Proceedings of the Job Scheduling Strategies for Parallel Processing, 2001

1999

Upper Bounds for MaxSat: Further Improved.

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