Nikhil Bansal

According to our database1, Nikhil Bansal authored at least 160 papers between 1999 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Nested Convex Bodies are Chaseable.
Algorithmica, 2020

Online vector balancing and geometric discrepancy.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

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

An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound.
SIAM J. Comput., 2019

Geometry of Scheduling on Multiple Machines.
CoRR, 2019

On-Line Balancing of Random Inputs.
CoRR, 2019

New Tools and Connections for Exponential-Time Approximation.
Algorithmica, 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

New Notions and Constructions of Sparsification for Graphs and Hypergraphs.
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.
SIAM J. Comput., 2018

On the Lovász Theta Function for Independent Sets in Sparse Graphs.
SIAM J. Comput., 2018

Tight Bounds for Double Coverage Against Weak Adversaries.
Theory Comput. Syst., 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

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. Sched., 2017

Tight approximation bounds for dominating set on graphs of bounded arboricity.
Inf. Process. Lett., 2017

Potential-Function Proofs for First-Order Methods.
CoRR, 2017

Competitive Algorithms for Generalized k-Server in Uniform Metrics.
CoRR, 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

The (h, k)-Server Problem on Bounded Depth Trees.
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

Minimizing Maximum Flow-Time on Related Machines.
Theory Comput., 2016

Weighted geometric set multi-cover via quasi-uniform sampling.
JoCG, 2016

Scheduling (Dagstuhl Seminar 16081).
Dagstuhl Reports, 2016

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

Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems.
CoRR, 2016

New Bounds for the $(h, k)$-Server Problem.
CoRR, 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

2015
Minimum Congestion Mapping in a Cloud.
SIAM J. Comput., 2015

On the adaptivity gap of stochastic orienteering.
Math. Program., 2015

A Polylogarithmic-Competitive Algorithm for the k-Server Problem.
J. ACM, 2015

On the number of matroids.
Combinatorica, 2015

Minimizing Flow-Time on Unrelated Machines.
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

2014
Better Scalable Algorithms for Broadcast Scheduling.
ACM Trans. Algorithms, 2014

A logarithmic approximation for unsplittable flow on line graphs.
ACM Trans. Algorithms, 2014

The Geometry of Scheduling.
SIAM J. Comput., 2014

Min-Max Graph Partitioning and Small Set Expansion.
SIAM J. Comput., 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

New Developments in Iterated Rounding (Invited Talk).
Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

2013
Speed Scaling with an Arbitrary Power Function.
ACM Trans. Algorithms, 2013

A Harmonic Algorithm for the 3D Strip Packing Problem.
SIAM J. Comput., 2013

On generalizations of network design problems with degree bounds.
Math. Program., 2013

Deterministic Discrepancy Minimization.
Algorithmica, 2013

2012
Regularity Lemmas and Combinatorial Algorithms.
Theory Comput., 2012

Solving Packing Integer Programs via Randomized Rounding with Alterations.
Theory Comput., 2012

Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule.
Theory Comput., 2012

Randomized Competitive Algorithms for Generalized Caching.
SIAM J. Comput., 2012

Semidefinite optimization in discrepancy theory.
Math. Program., 2012

A Primal-Dual Randomized Algorithm for Weighted Paging.
J. ACM, 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

2011
Competitive Algorithms for Due Date Scheduling.
Algorithmica, 2011

Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy.
Algorithmica, 2011

Average Rate Speed Scaling.
Algorithmica, 2011

A Polylogarithmic-Competitive Algorithm for the k-Server Problem.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On Capacitated Set Cover Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Dynamic pricing for impatient bidders.
ACM Trans. Algorithms, 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

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

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.
Wirel. Networks, 2009

Speed scaling with a solar cell.
Theor. Comput. Sci., 2009

Speed Scaling for Weighted Flow Time.
SIAM J. Comput., 2009

Additive Guarantees for Degree-Bounded Directed Network Design.
SIAM J. Comput., 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 Inf. Comput., 2009

On k-Column Sparse Packing Programs
CoRR, 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

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

Improved Approximation Algorithms for Broadcast Scheduling.
SIAM J. Comput., 2008

Robust reductions from ranking to classification.
Mach. Learn., 2008

SODA: An Optimizing Scheduler for Large-Scale Stream-Based Distributed Computer Systems.
Proceedings of the Middleware 2008, 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

2007
Minimizing weighted flow time.
ACM Trans. Algorithms, 2007

Speed scaling to manage energy and temperature.
J. ACM, 2007

Two-dimensional bin packing with one-dimensional resource augmentation.
Discret. Optim., 2007

Finding submasses in weighted strings with Fast Fourier Transform.
Discret. Appl. Math., 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

Harmonic algorithm for 3-dimensional strip packing problem.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Non-Preemptive Min-Sum Scheduling with Resource Augmentation.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching.
Proceedings of the Algorithms, 2007

2006
Handling load with less stress.
Queueing Syst. Theory Appl., 2006

Job Shop Scheduling with Unit Processing Times.
Math. Oper. Res., 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 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

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

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

Correlation Clustering.
Mach. Learn., 2004

Non-Clairvoyant Scheduling for Minimizing Mean Slowdown.
Algorithmica, 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 lp 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 Perform. Evaluation Rev., 2003

Analysis of the M/G/1 processor-sharing queue with bulk arrivals.
Oper. Res. Lett., 2003

Server scheduling in the Lp norm: a rising tide lifts all boat.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Online oblivious routing.
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.
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

2001
Analysis of M/G/1/SRPT under transient overload.
SIGMETRICS Perform. Evaluation Rev., 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


  Loading...