% csauthors.net - beta - BibTeX bibliography of Nikhil Bansal 001
@inproceedings{conf/isaac/BansalR99,
title = {Upper Bounds for MaxSat: Further Improved.},
year = {1999},
booktitle = {ISAAC},
author = {{Nikhil Bansal 001} and {Venkatesh Raman 001}},
publisher = {Springer},
booktitle = {Algorithms and Computation, 10th International Symposium, ISAAC '99, Chennai, India, December 16-18, 1999, Proceedings}
}
@inproceedings{conf/jsspp/Harchol-BalterBSA01,
title = {SRPT Scheduling for Web Servers.},
year = {2001},
booktitle = {JSSPP},
author = {{Mor Harchol-Balter} and {Nikhil Bansal 001} and {Bianca Schroeder} and {Mukesh Agrawal 002}},
publisher = {Springer},
booktitle = {Job Scheduling Strategies for Parallel Processing, 7th International Workshop, JSSPP 2001, Cambridge, MA, USA, June 16, 2001, Revised Papers}
}
@inproceedings{conf/sigmetrics/BansalH01,
title = {Analysis of SRPT scheduling: investigating unfairness.},
year = {2001},
booktitle = {SIGMETRICS/Performance},
author = {{Nikhil Bansal 001} and {Mor Harchol-Balter}},
publisher = {ACM},
booktitle = {Proceedings of the Joint International Conference on Measurements and Modeling of Computer Systems, SIGMETRICS/Performance 2001, June 16-20, 2001, Cambridge, MA, USA}
}
@article{journals/sigmetrics/BansalH01,
title = {Analysis of M/G/1/SRPT under transient overload.},
year = {2001},
journal = {SIGMETRICS Perform. Evaluation Rev.},
author = {{Nikhil Bansal 001} and {Mor Harchol-Balter}}
}
@inproceedings{conf/ifipTCS/BansalLS02,
title = {Bin-Packing with Fragile Objects.},
year = {2002},
booktitle = {IFIP TCS},
author = {{Nikhil Bansal 001} and {Zhen Liu} and {Arvind Sankar}},
publisher = {Kluwer},
booktitle = {Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002), August 25-30, 2002, Montréal, Québec, Canada}
}
@inproceedings{conf/esa/BansalBCD03,
title = {Scheduling for Flow-Time with Admission Control.},
year = {2003},
booktitle = {ESA},
author = {{Nikhil Bansal 001} and {Avrim Blum} and {Shuchi Chawla 001} and {Kedar Dhamdhere}},
publisher = {Springer},
booktitle = {Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings}
}
@inproceedings{conf/infocom/AgrawalMBS03,
title = {Improving Web Performance in Broadcast-Unicast Networks.},
year = {2003},
booktitle = {INFOCOM},
author = {{Mukesh Agrawal 002} and {Amit Manjhi} and {Nikhil Bansal 001} and {Srinivasan Seshan}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30 - April 3, 2003}
}
@inproceedings{conf/infocom/BansalL03,
title = {Capacity, Delay and Mobility in Wireless Ad-Hoc Networks.},
year = {2003},
booktitle = {INFOCOM},
author = {{Nikhil Bansal 001} and {Zhen Liu}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30 - April 3, 2003}
}
@inproceedings{conf/spaa/BansalBCM03,
title = {Online oblivious routing.},
year = {2003},
booktitle = {SPAA},
author = {{Nikhil Bansal 001} and {Avrim Blum} and {Shuchi Chawla 001} and {Adam Meyerson}},
publisher = {ACM},
booktitle = {SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, June 7-9, 2003, San Diego, California, USA (part of FCRC 2003)}
}
@inproceedings{conf/stoc/BansalP03,
title = {Server scheduling in the Lp norm: a rising tide lifts all boat.},
year = {2003},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Kirk Pruhs}},
publisher = {ACM},
booktitle = {Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA}
}
@article{journals/orl/Bansal03,
title = {Analysis of the M/G/1 processor-sharing queue with bulk arrivals.},
year = {2003},
journal = {Oper. Res. Lett.},
author = {{Nikhil Bansal 001}}
}
@article{journals/sigmetrics/Bansal03,
title = {On the average sojourn time under M/M/1/SRPT.},
year = {2003},
journal = {SIGMETRICS Perform. Evaluation Rev.},
author = {{Nikhil Bansal 001}}
}
@article{journals/tocs/Harchol-BalterSBA03,
title = {Size-based scheduling to improve web performance.},
year = {2003},
journal = {ACM Trans. Comput. Syst.},
author = {{Mor Harchol-Balter} and {Bianca Schroeder} and {Nikhil Bansal 001} and {Mukesh Agrawal 002}}
}
@inproceedings{conf/cpm/BansalCL04,
title = {Efficient Algorithms for Finding Submasses in Weighted Strings.},
year = {2004},
booktitle = {CPM},
author = {{Nikhil Bansal 001} and {Mark Cieliebak} and {Zsuzsanna Lipták}},
publisher = {Springer},
booktitle = {Combinatorial Pattern Matching, 15th Annual Symposium, CPM 2004, Istanbul,Turkey, July 5-7, 2004, Proceedings}
}
@inproceedings{conf/focs/BansalKP04,
title = {Dynamic Speed Scaling to Manage Energy and Temperature.},
year = {2004},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Tracy Kimbrel} and {Kirk Pruhs}},
publisher = {IEEE Computer Society},
booktitle = {45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings}
}
@inproceedings{conf/icalp/BansalFKMSS04,
title = {Further Improvements in Competitive Guarantees for QoS Buffering.},
year = {2004},
booktitle = {ICALP},
author = {{Nikhil Bansal 001} and {Lisa Fleischer} and {Tracy Kimbrel} and {Mohammad Mahdian} and {Baruch Schieber} and {Maxim Sviridenko}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings}
}
@inproceedings{conf/latin/BansalP04,
title = {Server Scheduling in the Weighted lp Norm.},
year = {2004},
booktitle = {LATIN},
author = {{Nikhil Bansal 001} and {Kirk Pruhs}},
publisher = {Springer},
booktitle = {LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings}
}
@inproceedings{conf/soda/Bansal04,
title = {On minimizing the total flow time on multiple machines.},
year = {2004},
booktitle = {SODA},
author = {{Nikhil Bansal 001}},
publisher = {SIAM},
booktitle = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004}
}
@inproceedings{conf/soda/BansalS04,
title = {New approximability and inapproximability results for 2-dimensional Bin Packing.},
year = {2004},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Maxim Sviridenko}},
publisher = {SIAM},
booktitle = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004}
}
@inproceedings{conf/stoc/BansalBCM04,
title = {Approximation algorithms for deadline-TSP and vehicle routing with time-windows.},
year = {2004},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Avrim Blum} and {Shuchi Chawla 001} and {Adam Meyerson}},
publisher = {ACM},
booktitle = {Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004}
}
@article{journals/algorithmica/BansalDKS04,
title = {Non-Clairvoyant Scheduling for Minimizing Mean Slowdown.},
year = {2004},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Kedar Dhamdhere} and {Jochen Könemann} and {Amitabh Sinha}}
}
@article{journals/ml/BansalBC04,
title = {Correlation Clustering.},
year = {2004},
journal = {Mach. Learn.},
author = {{Nikhil Bansal 001} and {Avrim Blum} and {Shuchi Chawla 001}}
}
@article{journals/orl/WiermanBH04,
title = {A note on comparing response times in the M/GI/1/FB and M/GI/1/PS queues.},
year = {2004},
journal = {Oper. Res. Lett.},
author = {{Adam Wierman} and {Nikhil Bansal 001} and {Mor Harchol-Balter}}
}
@inproceedings{conf/focs/BansalLS05,
title = {A Tale of Two Dimensional Bin Packing.},
year = {2005},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Andrea Lodi 001} and {Maxim Sviridenko}},
publisher = {IEEE Computer Society},
booktitle = {46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings}
}
@inproceedings{conf/soda/BansalCKN05,
title = {Approximating the average response time in broadcast scheduling.},
year = {2005},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Moses Charikar} and {Sanjeev Khanna} and {Joseph Naor}},
publisher = {SIAM},
booktitle = {Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005}
}
@inproceedings{conf/stacs/BansalP05,
title = {Speed Scaling to Manage Temperature.},
year = {2005},
booktitle = {STACS},
author = {{Nikhil Bansal 001} and {Kirk Pruhs}},
publisher = {Springer},
booktitle = {STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings}
}
@article{journals/mor/BansalMS05,
title = {Minimizing Makespan in No-Wait Job Shops.},
year = {2005},
journal = {Math. Oper. Res.},
author = {{Nikhil Bansal 001} and {Mohammad Mahdian} and {Maxim Sviridenko}}
}
@article{journals/orl/Bansal05a,
title = {Minimizing flow time on a constant number of machines with preemption.},
year = {2005},
journal = {Oper. Res. Lett.},
author = {{Nikhil Bansal 001}}
}
@inproceedings{conf/approx/BansalCS06,
title = {Minimizing Setup and Beam-On Times in Radiation Therapy.},
year = {2006},
booktitle = {APPROX-RANDOM},
author = {{Nikhil Bansal 001} and {Don Coppersmith} and {Baruch Schieber}},
publisher = {Springer},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings}
}
@inproceedings{conf/focs/BansalCS06,
title = {Improved approximation algorithms for multidimensional bin packing problems.},
year = {2006},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Alberto Caprara} and {Maxim Sviridenko}},
publisher = {IEEE Computer Society},
booktitle = {47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings}
}
@inproceedings{conf/stoc/BansalCES06,
title = {A quasi-PTAS for unsplittable flow on line graphs.},
year = {2006},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Amit Chakrabarti} and {Amir Epstein} and {Baruch Schieber}},
publisher = {ACM},
booktitle = {Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006}
}
@inproceedings{conf/stoc/BansalS06,
title = {The Santa Claus problem.},
year = {2006},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Maxim Sviridenko}},
publisher = {ACM},
booktitle = {Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006}
}
@article{journals/mor/BansalCKS06,
title = {Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes.},
year = {2006},
journal = {Math. Oper. Res.},
author = {{Nikhil Bansal 001} and {José R. Correa} and {Claire Kenyon} and {Maxim Sviridenko}}
}
@article{journals/mor/BansalKS06,
title = {Job Shop Scheduling with Unit Processing Times.},
year = {2006},
journal = {Math. Oper. Res.},
author = {{Nikhil Bansal 001} and {Tracy Kimbrel} and {Maxim Sviridenko}}
}
@article{journals/questa/BansalG06,
title = {Handling load with less stress.},
year = {2006},
journal = {Queueing Syst. Theory Appl.},
author = {{Nikhil Bansal 001} and {David Gamarnik}}
}
@inproceedings{conf/esa/BansalBGN07,
title = {An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching.},
year = {2007},
booktitle = {ESA},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Anupam Gupta 001} and {Joseph Naor}},
publisher = {Springer},
booktitle = {Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings}
}
@inproceedings{conf/focs/BansalCKPSS07,
title = {Non-Preemptive Min-Sum Scheduling with Resource Augmentation.},
year = {2007},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Ho-Leung Chan} and {Rohit Khandekar} and {Kirk Pruhs} and {Clifford Stein 001} and {Baruch Schieber}},
publisher = {IEEE Computer Society},
booktitle = {48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings}
}
@inproceedings{conf/soda/BansalHISZ07,
title = {Harmonic algorithm for 3-dimensional strip packing problem.},
year = {2007},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Xin Han} and {Kazuo Iwama} and {Maxim Sviridenko} and {Guochuan Zhang}},
publisher = {SIAM},
booktitle = {Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007}
}
@article{journals/dam/BansalCL07,
title = {Finding submasses in weighted strings with Fast Fourier Transform.},
year = {2007},
journal = {Discret. Appl. Math.},
author = {{Nikhil Bansal 001} and {Mark Cieliebak} and {Zsuzsanna Lipták}}
}
@article{journals/disopt/BansalS07,
title = {Two-dimensional bin packing with one-dimensional resource augmentation.},
year = {2007},
journal = {Discret. Optim.},
author = {{Nikhil Bansal 001} and {Maxim Sviridenko}}
}
@article{journals/jacm/BansalKP07,
title = {Speed scaling to manage energy and temperature.},
year = {2007},
journal = {J. ACM},
author = {{Nikhil Bansal 001} and {Tracy Kimbrel} and {Kirk Pruhs}}
}
@article{journals/talg/BansalD07,
title = {Minimizing weighted flow time.},
year = {2007},
journal = {ACM Trans. Algorithms},
author = {{Nikhil Bansal 001} and {Kedar Dhamdhere}}
}
@inproceedings{conf/icalp/BansalCLL08,
title = {Scheduling for Speed Bounded Processors.},
year = {2008},
booktitle = {ICALP (1)},
author = {{Nikhil Bansal 001} and {Ho-Leung Chan} and {Tak Wah Lam} and {Lap-Kei Lee}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games}
}
@inproceedings{conf/infocom/BansalBJPTV08,
title = {Towards Optimal Resource Allocation in Partial-Fault Tolerant Applications.},
year = {2008},
booktitle = {INFOCOM},
author = {{Nikhil Bansal 001} and {Ranjita Bhagwan} and {Navendu Jain} and {Yoonho Park} and {Deepak S. Turaga} and {Chitra Venkatramani}},
publisher = {IEEE},
booktitle = {INFOCOM 2008. 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 13-18 April 2008, Phoenix, AZ, USA}
}
@inproceedings{conf/isi/PanjiyarMBSM08,
title = {Transport security using mobile technology.},
year = {2008},
booktitle = {ISI},
author = {{P. Panjiyar} and {P. Mourya} and {Nikhil Bansal 001} and {P. Srivastava} and {A. Mukherjee}},
publisher = {IEEE},
booktitle = {IEEE International Conference on Intelligence and Security Informatics, ISI 2008, Taipei, Taiwan, June 17-20, 2008, Proceedings}
}
@inproceedings{conf/middleware/WolfBHPRWWF08,
title = {SODA: An Optimizing Scheduler for Large-Scale Stream-Based Distributed Computer Systems.},
year = {2008},
booktitle = {Middleware},
author = {{Joel L. Wolf} and {Nikhil Bansal 001} and {Kirsten Hildrum} and {Sujay S. Parekh} and {Deepak Rajan} and {Rohit Wagle} and {Kun-Lung Wu} and {Lisa Fleischer}},
publisher = {Springer},
booktitle = {Middleware 2008, ACM/IFIP/USENIX 9th International Middleware Conference, Leuven, Belgium, December 1-5, 2008, Proceedings}
}
@article{journals/ml/BalcanBBCLS08,
title = {Robust reductions from ranking to classification.},
year = {2008},
journal = {Mach. Learn.},
author = {{Maria-Florina Balcan} and {Nikhil Bansal 001} and {Alina Beygelzimer} and {Don Coppersmith} and {John Langford 001} and {Gregory B. Sorkin}}
}
@article{journals/siamcomp/BansalCS08,
title = {Improved Approximation Algorithms for Broadcast Scheduling.},
year = {2008},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Don Coppersmith} and {Maxim Sviridenko}}
}
@incollection{reference/algo/Bansal08,
title = {Approximation Schemes for Bin Packing.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/Bansal08a,
title = {Minimum Flow Time.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/Bansal08b,
title = {Multi-level Feedback Queues.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/Bansal08c,
title = {Oblivious Routing.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/Bansal08d,
title = {Shortest Elapsed Time First Scheduling.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@inproceedings{conf/focs/BansalK09,
title = {Optimal Long Code Test with One Free Bit.},
year = {2009},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Subhash Khot}},
publisher = {IEEE Computer Society},
booktitle = {50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA}
}
@inproceedings{conf/isaac/BansalCJPS09,
title = {A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability.},
year = {2009},
booktitle = {ISAAC},
author = {{Nikhil Bansal 001} and {Alberto Caprara} and {Klaus Jansen} and {Lars Prädel} and {Maxim Sviridenko}},
publisher = {Springer},
booktitle = {Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings}
}
@inproceedings{conf/jsspp/WolfBHPRWW09,
title = {Job Admission and Resource Allocation in Distributed Streaming Systems.},
year = {2009},
booktitle = {JSSPP},
author = {{Joel L. Wolf} and {Nikhil Bansal 001} and {Kirsten Hildrum} and {Sujay S. Parekh} and {Deepak Rajan} and {Rohit Wagle} and {Kun-Lung Wu}},
publisher = {Springer},
booktitle = {Job Scheduling Strategies for Parallel Processing, 14th International Workshop, JSSPP 2009, Rome, Italy, May 29, 2009. Revised Papers}
}
@inproceedings{conf/soda/BansalC09,
title = {Weighted flow time does not admit O(1)-competitive algorithms.},
year = {2009},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Ho-Leung Chan}},
publisher = {SIAM},
booktitle = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009}
}
@article{journals/corr/abs-0908-2256,
title = {On k-Column Sparse Packing Programs},
year = {2009},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Nitish Korula} and {Viswanath Nagarajan}}
}
@article{journals/qic/BansalBT09,
title = {Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs.},
year = {2009},
journal = {Quantum Inf. Comput.},
author = {{Nikhil Bansal 001} and {Sergey Bravyi 001} and {Barbara M. Terhal}}
}
@article{journals/siamcomp/BansalCS09,
title = {A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing.},
year = {2009},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Alberto Caprara} and {Maxim Sviridenko}}
}
@article{journals/siamcomp/BansalKN09,
title = {Additive Guarantees for Degree-Bounded Directed Network Design.},
year = {2009},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Rohit Khandekar} and {Viswanath Nagarajan}}
}
@article{journals/siamcomp/BansalPS09,
title = {Speed Scaling for Weighted Flow Time.},
year = {2009},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Kirk Pruhs} and {Clifford Stein 001}}
}
@article{journals/tcs/BansalCP09,
title = {Speed scaling with a solar cell.},
year = {2009},
journal = {Theor. Comput. Sci.},
author = {{Nikhil Bansal 001} and {Ho-Leung Chan} and {Kirk Pruhs}}
}
@article{journals/winet/BansalLS09,
title = {Bin-packing with fragile objects and frequency allocation in cellular networks.},
year = {2009},
journal = {Wirel. Networks},
author = {{Nikhil Bansal 001} and {Zhen Liu} and {Arvind Sankar}}
}
@inproceedings{conf/esa/BansalGLMNR10,
title = {When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract).},
year = {2010},
booktitle = {ESA (2)},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001} and {Jian Li 015} and {Julián Mestre} and {Viswanath Nagarajan} and {Atri Rudra}},
publisher = {Springer},
booktitle = {Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II}
}
@inproceedings{conf/focs/Bansal10,
title = {Constructive Algorithms for Discrepancy Minimization.},
year = {2010},
booktitle = {FOCS},
author = {{Nikhil Bansal 001}},
publisher = {IEEE Computer Society},
booktitle = {51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA}
}
@inproceedings{conf/icalp/BansalBN10,
title = {Metrical Task Systems and the k-Server Problem on HSTs.},
year = {2010},
booktitle = {ICALP (1)},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Joseph Naor}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I}
}
@inproceedings{conf/icalp/BansalJKN10,
title = {Approximation Algorithms for Diversified Search Ranking.},
year = {2010},
booktitle = {ICALP (2)},
author = {{Nikhil Bansal 001} and {Kamal Jain} and {Anna Kazeykina} and {Joseph Naor}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II}
}
@inproceedings{conf/icalp/BansalK10,
title = {Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.},
year = {2010},
booktitle = {ICALP (1)},
author = {{Nikhil Bansal 001} and {Subhash Khot}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I}
}
@inproceedings{conf/ipco/BansalKNS10,
title = {On k-Column Sparse Packing Programs.},
year = {2010},
booktitle = {IPCO},
author = {{Nikhil Bansal 001} and {Nitish Korula} and {Viswanath Nagarajan} and {Aravind Srinivasan}},
publisher = {Springer},
booktitle = {Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings}
}
@inproceedings{conf/soda/BansalBN10,
title = {Towards the Randomized k-Server Conjecture: A Primal-Dual Approach.},
year = {2010},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Joseph Naor}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010}
}
@inproceedings{conf/soda/BansalGK10,
title = {A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover.},
year = {2010},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001} and {Ravishankar Krishnaswamy}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010}
}
@article{journals/algorithmica/BansalLMZ10,
title = {On the Longest Common Rigid Subsequence Problem.},
year = {2010},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Moshe Lewenstein} and {Bin Ma 002} and {Kaizhong Zhang}}
}
@article{journals/siamcomp/BansalP10,
title = {Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service.},
year = {2010},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Kirk Pruhs}}
}
@article{journals/talg/BansalCCRSS10,
title = {Dynamic pricing for impatient bidders.},
year = {2010},
journal = {ACM Trans. Algorithms},
author = {{Nikhil Bansal 001} and {Ning Chen} and {Neva Cherniavsky} and {Atri Rudra} and {Baruch Schieber} and {Maxim Sviridenko}}
}
@inproceedings{conf/approx/BansalKS11,
title = {On Capacitated Set Cover Problems.},
year = {2011},
booktitle = {APPROX-RANDOM},
author = {{Nikhil Bansal 001} and {Ravishankar Krishnaswamy} and {Barna Saha}},
publisher = {Springer},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings}
}
@inproceedings{conf/focs/BansalBMN11,
title = {A Polylogarithmic-Competitive Algorithm for the k-Server Problem.},
year = {2011},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Aleksander Madry} and {Joseph Naor}},
publisher = {IEEE Computer Society},
booktitle = {IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011}
}
@article{journals/algorithmica/BansalBCP11,
title = {Average Rate Speed Scaling.},
year = {2011},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {David P. Bunde} and {Ho-Leung Chan} and {Kirk Pruhs}}
}
@article{journals/algorithmica/BansalCCHLMSW11,
title = {Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy.},
year = {2011},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Danny Z. Chen} and {Don Coppersmith} and {Xiaobo Sharon Hu} and {Shuang Luan} and {Ewa Misiolek} and {Baruch Schieber} and {Chao Wang 002}}
}
@article{journals/algorithmica/BansalCP11,
title = {Competitive Algorithms for Due Date Scheduling.},
year = {2011},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Ho-Leung Chan} and {Kirk Pruhs}}
}
@inproceedings{conf/medalg/BansalGKNPS12,
title = {Multicast Routing for Energy Minimization Using Speed Scaling.},
year = {2012},
booktitle = {MedAlg},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001} and {Ravishankar Krishnaswamy} and {Viswanath Nagarajan} and {Kirk Pruhs} and {Cliff Stein 001}},
publisher = {Springer},
booktitle = {Design and Analysis of Algorithms - First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proceedings}
}
@inproceedings{conf/stoc/BansalBJK12,
title = {Tight time-space tradeoff for mutual exclusion.},
year = {2012},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Vibhor Bhatt} and {Prasad Jayanti} and {Ranganath Kondapally}},
publisher = {ACM},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012}
}
@inproceedings{conf/waoa/Bansal12,
title = {The Primal-Dual Approach for Online Algorithms.},
year = {2012},
booktitle = {WAOA},
author = {{Nikhil Bansal 001}},
publisher = {Springer},
booktitle = {Approximation and Online Algorithms - 10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers}
}
@article{journals/algorithmica/BansalGLMNR12,
title = {When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings.},
year = {2012},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001} and {Jian Li 015} and {Julián Mestre} and {Viswanath Nagarajan} and {Atri Rudra}}
}
@article{journals/jacm/BansalBN12,
title = {A Primal-Dual Randomized Algorithm for Weighted Paging.},
year = {2012},
journal = {J. ACM},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Joseph Naor}}
}
@article{journals/mp/Bansal12,
title = {Semidefinite optimization in discrepancy theory.},
year = {2012},
journal = {Math. Program.},
author = {{Nikhil Bansal 001}}
}
@article{journals/siamcomp/BansalBN12,
title = {Randomized Competitive Algorithms for Generalized Caching.},
year = {2012},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Joseph Naor}}
}
@article{journals/toc/BansalCKP12,
title = {Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule.},
year = {2012},
journal = {Theory Comput.},
author = {{Nikhil Bansal 001} and {Ho-Leung Chan} and {Dmitriy Katz} and {Kirk Pruhs}}
}
@article{journals/toc/BansalKNS12,
title = {Solving Packing Integer Programs via Randomized Rounding with Alterations.},
year = {2012},
journal = {Theory Comput.},
author = {{Nikhil Bansal 001} and {Nitish Korula} and {Viswanath Nagarajan} and {Aravind Srinivasan}}
}
@article{journals/toc/BansalW12,
title = {Regularity Lemmas and Combinatorial Algorithms.},
year = {2012},
journal = {Theory Comput.},
author = {{Nikhil Bansal 001} and {Ryan Williams 001}}
}
@article{journals/algorithmica/BansalS13,
title = {Deterministic Discrepancy Minimization.},
year = {2013},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Joel Spencer}}
}
@article{journals/mp/BansalKKNP13,
title = {On generalizations of network design problems with degree bounds.},
year = {2013},
journal = {Math. Program.},
author = {{Nikhil Bansal 001} and {Rohit Khandekar} and {Jochen Könemann} and {Viswanath Nagarajan} and {Britta Peis}}
}
@article{journals/siamcomp/BansalHISZ13,
title = {A Harmonic Algorithm for the 3D Strip Packing Problem.},
year = {2013},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Xin Han} and {Kazuo Iwama} and {Maxim Sviridenko} and {Guochuan Zhang}}
}
@article{journals/talg/BansalCP13,
title = {Speed Scaling with an Arbitrary Power Function.},
year = {2013},
journal = {ACM Trans. Algorithms},
author = {{Nikhil Bansal 001} and {Ho-Leung Chan} and {Kirk Pruhs}}
}
@inproceedings{conf/fsttcs/Bansal14,
title = {New Developments in Iterated Rounding (Invited Talk).},
year = {2014},
booktitle = {FSTTCS},
author = {{Nikhil Bansal 001}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India}
}
@inproceedings{conf/latin/BansalRSVZ14,
title = {Approximating Real-Time Scheduling on Identical Machines.},
year = {2014},
booktitle = {LATIN},
author = {{Nikhil Bansal 001} and {Cyriel Rutten} and {Suzanne van der Ster} and {Tjark Vredeveld} and {Ruben van der Zwaan}},
publisher = {Springer},
booktitle = {LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings}
}
@inproceedings{conf/latin/BansalVZ14,
title = {Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.},
year = {2014},
booktitle = {LATIN},
author = {{Nikhil Bansal 001} and {Tjark Vredeveld} and {Ruben van der Zwaan}},
publisher = {Springer},
booktitle = {LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings}
}
@inproceedings{conf/soda/BansalCKL14,
title = {Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach.},
year = {2014},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Moses Charikar} and {Ravishankar Krishnaswamy} and {Shi Li 001}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014}
}
@inproceedings{conf/soda/BansalK14,
title = {Improved Approximation Algorithm for Two-Dimensional Bin Packing.},
year = {2014},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Arindam Khan 001}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014}
}
@article{journals/algorithmica/BansalBGN14,
title = {A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching.},
year = {2014},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Anupam Gupta 001} and {Joseph Naor}}
}
@article{journals/jct/BansalPP14,
title = {An entropy argument for counting matroids.},
year = {2014},
journal = {J. Comb. Theory, Ser. B},
author = {{Nikhil Bansal 001} and {Rudi Pendavingh} and {Jorn G. van der Pol}}
}
@article{journals/siamcomp/BansalFKMNNS14,
title = {Min-Max Graph Partitioning and Small Set Expansion.},
year = {2014},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Uriel Feige} and {Robert Krauthgamer} and {Konstantin Makarychev} and {Viswanath Nagarajan} and {Joseph Naor} and {Roy Schwartz 002}}
}
@article{journals/siamcomp/BansalP14,
title = {The Geometry of Scheduling.},
year = {2014},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Kirk Pruhs}}
}
@article{journals/talg/BansalFKS14,
title = {A logarithmic approximation for unsplittable flow on line graphs.},
year = {2014},
journal = {ACM Trans. Algorithms},
author = {{Nikhil Bansal 001} and {Zachary Friggstad} and {Rohit Khandekar} and {Mohammad R. Salavatipour}}
}
@article{journals/talg/BansalKN14,
title = {Better Scalable Algorithms for Broadcast Scheduling.},
year = {2014},
journal = {ACM Trans. Algorithms},
author = {{Nikhil Bansal 001} and {Ravishankar Krishnaswamy} and {Viswanath Nagarajan}}
}
@inproceedings{conf/approx/BansalGKPSS15,
title = {A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs.},
year = {2015},
booktitle = {APPROX-RANDOM},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001} and {Ravishankar Krishnaswamy} and {Kirk Pruhs} and {Kevin Schewior} and {Clifford Stein 001}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA}
}
@inproceedings{conf/soda/Bansal15,
title = {Approximating independent sets in sparse graphs.},
year = {2015},
booktitle = {SODA},
author = {{Nikhil Bansal 001}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015}
}
@inproceedings{conf/stoc/BansalK15,
title = {Minimizing Flow-Time on Unrelated Machines.},
year = {2015},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Janardhan Kulkarni}},
publisher = {ACM},
booktitle = {Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015}
}
@article{journals/combinatorica/BansalPP15,
title = {On the number of matroids.},
year = {2015},
journal = {Comb.},
author = {{Nikhil Bansal 001} and {Rudi Pendavingh} and {Jorn G. van der Pol}}
}
@article{journals/jacm/BansalBMN15,
title = {A Polylogarithmic-Competitive Algorithm for the k-Server Problem.},
year = {2015},
journal = {J. ACM},
author = {{Nikhil Bansal 001} and {Niv Buchbinder} and {Aleksander Madry} and {Joseph Naor}}
}
@article{journals/mp/BansalN15,
title = {On the adaptivity gap of stochastic orienteering.},
year = {2015},
journal = {Math. Program.},
author = {{Nikhil Bansal 001} and {Viswanath Nagarajan}}
}
@article{journals/siamcomp/BansalLNZ15,
title = {Minimum Congestion Mapping in a Cloud.},
year = {2015},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Kang-Won Lee} and {Viswanath Nagarajan} and {Murtaza Zafer}}
}
@inproceedings{conf/ipco/BansalN16,
title = {Approximation-Friendly Discrepancy Rounding.},
year = {2016},
booktitle = {IPCO},
author = {{Nikhil Bansal 001} and {Viswanath Nagarajan}},
publisher = {Springer},
booktitle = {Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings}
}
@inproceedings{conf/soda/BansalE016,
title = {Improved Approximation for Vector Bin Packing.},
year = {2016},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Arindam Khan 001}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016}
}
@article{journals/algorithmica/BansalOVZ16,
title = {Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.},
year = {2016},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Tim Oosterwijk} and {Tjark Vredeveld} and {Ruben van der Zwaan}}
}
@article{journals/corr/BansalEJK16,
title = {New Bounds for the \$(h, k)\$-Server Problem.},
year = {2016},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Lukasz Jez} and {Grigorios Koumoutsos}}
}
@article{journals/corr/BansalG16,
title = {Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems.},
year = {2016},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Shashwat Garg}}
}
@article{journals/corr/BansalRU16,
title = {Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.},
year = {2016},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Daniel Reichman 001} and {Seeun William Umboh}}
}
@article{journals/dagstuhl-reports/BansalMS16,
title = {Scheduling (Dagstuhl Seminar 16081).},
year = {2016},
journal = {Dagstuhl Reports},
author = {{Nikhil Bansal 001} and {Nicole Megow} and {Clifford Stein 001}}
}
@article{journals/jocg/BansalP16,
title = {Weighted geometric set multi-cover via quasi-uniform sampling.},
year = {2016},
journal = {J. Comput. Geom.},
author = {{Nikhil Bansal 001} and {Kirk Pruhs}}
}
@article{journals/toc/BansalC16,
title = {Minimizing Maximum Flow-Time on Related Machines.},
year = {2016},
journal = {Theory Comput.},
author = {{Nikhil Bansal 001} and {Bouke Cloostermans}}
}
@incollection{reference/algo/Bansal16,
title = {Approximation Schemes for Bin Packing.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}}
}
@incollection{reference/algo/Bansal16a,
title = {Minimum Flow Time.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}}
}
@incollection{reference/algo/Bansal16b,
title = {Multilevel Feedback Queues.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}}
}
@incollection{reference/algo/Bansal16c,
title = {Oblivious Routing.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}}
}
@incollection{reference/algo/Bansal16d,
title = {Shortest Elapsed Time First Scheduling.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Nikhil Bansal 001}}
}
@inproceedings{conf/focs/BansalEK17,
title = {Weighted k-Server Bounds via Combinatorial Dichotomies.},
year = {2017},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Grigorios Koumoutsos}},
publisher = {IEEE Computer Society},
booktitle = {58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017}
}
@inproceedings{conf/soda/Bansal0U17,
title = {LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs.},
year = {2017},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Daniel Reichman 001} and {Seeun William Umboh}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19}
}
@inproceedings{conf/soda/BansalEJK17,
title = {The (h, k)-Server Problem on Bounded Depth Trees.},
year = {2017},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Lukasz Jez} and {Grigorios Koumoutsos}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19}
}
@inproceedings{conf/stoc/BansalG17,
title = {Algorithmic discrepancy beyond partial coloring.},
year = {2017},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Shashwat Garg}},
publisher = {ACM},
booktitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017}
}
@inproceedings{conf/stoc/BansalGNV17,
title = {Faster space-efficient algorithms for subset sum and k-sum.},
year = {2017},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Shashwat Garg} and {Jesper Nederlof} and {Nikhil Vyas 001}},
publisher = {ACM},
booktitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017}
}
@article{journals/algorithmica/BansalF17,
title = {Guest Editors' Foreword.},
year = {2017},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Irene Finocchi}}
}
@article{journals/corr/BansalEKN17,
title = {Competitive Algorithms for Generalized k-Server in Uniform Metrics.},
year = {2017},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Grigorios Koumoutsos} and {Jesper Nederlof}}
}
@article{journals/corr/abs-1712-04581,
title = {Potential-Function Proofs for First-Order Methods.},
year = {2017},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001}}
}
@article{journals/ipl/BansalU17,
title = {Tight approximation bounds for dominating set on graphs of bounded arboricity.},
year = {2017},
journal = {Inf. Process. Lett.},
author = {{Nikhil Bansal 001} and {Seeun William Umboh}}
}
@article{journals/scheduling/BansalDTV17,
title = {The local-global conjecture for scheduling with non-linear cost.},
year = {2017},
journal = {J. Sched.},
author = {{Nikhil Bansal 001} and {Christoph Dürr} and {Kim Thang Nguyen} and {Óscar C. Vásquez}}
}
@inproceedings{conf/isaac/ChenBCB18,
title = {Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems.},
year = {2018},
booktitle = {ISAAC},
author = {{Jian-Jia Chen} and {Nikhil Bansal 001} and {Samarjit Chakraborty} and {Georg von der Brüggen}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan}
}
@article{journals/mor/BansalKZ18,
title = {Achievable Performance of Blind Policies in Heavy Traffic.},
year = {2018},
journal = {Math. Oper. Res.},
author = {{Nikhil Bansal 001} and {Bart Kamphorst} and {Bert Zwart}}
}
@article{journals/mst/BansalEJKP18,
title = {Tight Bounds for Double Coverage Against Weak Adversaries.},
year = {2018},
journal = {Theory Comput. Syst.},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Lukasz Jez} and {Grigorios Koumoutsos} and {Kirk Pruhs}}
}
@article{journals/siamcomp/BansalGG18,
title = {On the Lovász Theta Function for Independent Sets in Sparse Graphs.},
year = {2018},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001} and {Guru Guruganesh}}
}
@article{journals/siamcomp/BansalGN018,
title = {Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems.},
year = {2018},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Shashwat Garg} and {Jesper Nederlof} and {Nikhil Vyas 001}}
}
@inproceedings{conf/focs/BansalST19,
title = {New Notions and Constructions of Sparsification for Graphs and Hypergraphs.},
year = {2019},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {Ola Svensson} and {Luca Trevisan}},
publisher = {IEEE Computer Society},
booktitle = {60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019}
}
@inproceedings{conf/stoc/Bansal19,
title = {On a generalization of iterated and randomized rounding.},
year = {2019},
booktitle = {STOC},
author = {{Nikhil Bansal 001}},
publisher = {ACM},
booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019.}
}
@article{journals/algorithmica/BansalCLNN19,
title = {New Tools and Connections for Exponential-Time Approximation.},
year = {2019},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Parinya Chalermsook} and {Bundit Laekhanukit} and {Danupon Nanongkai} and {Jesper Nederlof}}
}
@article{journals/corr/abs-1907-05473,
title = {Geometry of Scheduling on Multiple Machines.},
year = {2019},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Jatin Batra}}
}
@article{journals/siamcomp/BansalDG19,
title = {An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound.},
year = {2019},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Daniel Dadush} and {Shashwat Garg}}
}
@article{journals/talg/BansalEJK19,
title = {The (h, k)-Server Problem on Bounded Depth Trees.},
year = {2019},
journal = {ACM Trans. Algorithms},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Lukasz Jez} and {Grigorios Koumoutsos}}
}
@article{journals/toc/BansalDGL19,
title = {The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues.},
year = {2019},
journal = {Theory Comput.},
author = {{Nikhil Bansal 001} and {Daniel Dadush} and {Shashwat Garg} and {Shachar Lovett}}
}
@article{journals/toc/BansalG19,
title = {Potential-Function Proofs for Gradient Methods.},
year = {2019},
journal = {Theory Comput.},
author = {{Nikhil Bansal 001} and {Anupam Gupta 001}}
}
@inproceedings{conf/stoc/BansalJ0S20,
title = {Online vector balancing and geometric discrepancy.},
year = {2020},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Haotian Jiang} and {Sahil Singla 001} and {Makrand Sinha}},
publisher = {ACM},
booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020}
}
@article{journals/algorithmica/BansalBEKU20,
title = {Nested Convex Bodies are Chaseable.},
year = {2020},
journal = {Algorithmica},
author = {{Nikhil Bansal 001} and {Martin Böhm 001} and {Marek Eliás 001} and {Grigorios Koumoutsos} and {Seeun William Umboh}}
}
@article{journals/corr/abs-2007-15709,
title = {An Asymptotic Lower Bound for Online Vector Bin Packing.},
year = {2020},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Ilan Reuven Cohen}}
}
@article{journals/corr/abs-2011-09076,
title = {Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging.},
year = {2020},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Christian Coester} and {Ravi Kumar 001} and {Manish Purohit} and {Erik Vee}}
}
@article{journals/eatcs/AlbersBMMNNPSS20,
title = {EATCS Distinguished Dissertation Award 2020 - Call for Nominations.},
year = {2020},
journal = {Bull. EATCS},
author = {{Susanne Albers} and {Nikhil Bansal 001} and {Elvira Mayordomo} and {Dale Miller 001} and {Jaroslav Nesetril} and {Damian Niwinski} and {David Peleg} and {Vladimiro Sassone} and {Alexandra Silva 001}}
}
@article{journals/eccc/BansalS20,
title = {\$k\$-Forrelation Optimally Separates Quantum and Classical Query Complexity.},
year = {2020},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Nikhil Bansal 001} and {Makrand Sinha}}
}
@article{journals/rsa/BansalM20,
title = {On the discrepancy of random low degree set systems.},
year = {2020},
journal = {Random Struct. Algorithms},
author = {{Nikhil Bansal 001} and {Raghu Meka}}
}
@article{journals/rsa/BansalS20,
title = {On-line balancing of random inputs.},
year = {2020},
journal = {Random Struct. Algorithms},
author = {{Nikhil Bansal 001} and {Joel H. Spencer}}
}
@inproceedings{conf/soda/BansalB21,
title = {Non-uniform Geometric Set Cover and Scheduling on Multiple Machines.},
year = {2021},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Jatin Batra}},
publisher = {SIAM},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021}
}
@inproceedings{conf/soda/BansalBFT21,
title = {Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover.},
year = {2021},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Jatin Batra} and {Majid Farhadi} and {Prasad Tetali}},
publisher = {SIAM},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021}
}
@inproceedings{conf/soda/BansalJMSS21,
title = {Online Discrepancy Minimization for Stochastic Arrivals.},
year = {2021},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Haotian Jiang} and {Raghu Meka} and {Sahil Singla 001} and {Makrand Sinha}},
publisher = {SIAM},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021}
}
@inproceedings{conf/spaa/BansalNT21,
title = {Efficient Online Weighted Multi-Level Paging.},
year = {2021},
booktitle = {SPAA},
author = {{Nikhil Bansal 001} and {Joseph (Seffi) Naor} and {Ohad Talmon}},
publisher = {ACM},
booktitle = {SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021}
}
@inproceedings{conf/waoa/BansalC21,
title = {Contention Resolution, Matrix Scaling and Fair Allocation.},
year = {2021},
booktitle = {WAOA},
author = {{Nikhil Bansal 001} and {Ilan Reuven Cohen}},
publisher = {Springer},
booktitle = {Approximation and Online Algorithms - 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6-10, 2021, Revised Selected Papers}
}
@article{journals/corr/abs-2106-06051,
title = {Well-Balanced Allocation on General Graphs.},
year = {2021},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Ohad N. Feldheim}}
}
@article{journals/corr/abs-2111-15169,
title = {Online metric allocation.},
year = {2021},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Christian Coester}}
}
@article{journals/siamcomp/BansalSS21,
title = {Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines.},
year = {2021},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Aravind Srinivasan} and {Ola Svensson}}
}
@inproceedings{conf/approx/BansalLV22,
title = {A Unified Approach to Discrepancy Minimization.},
year = {2022},
booktitle = {APPROX/RANDOM},
author = {{Nikhil Bansal 001} and {Aditi Laddha} and {Santosh S. Vempala}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference).}
}
@inproceedings{conf/coco/0001SW22,
title = {Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms.},
year = {2022},
booktitle = {CCC},
author = {{Nikhil Bansal 001} and {Makrand Sinha} and {Ronald de Wolf}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA.}
}
@inproceedings{conf/esa/0001C22,
title = {Online Metric Allocation and Time-Varying Regularization.},
year = {2022},
booktitle = {ESA},
author = {{Nikhil Bansal 001} and {Christian Coester}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany.}
}
@inproceedings{conf/focs/0001K22,
title = {Balanced Allocations: The Heavily Loaded Case with Deletions.},
year = {2022},
booktitle = {FOCS},
author = {{Nikhil Bansal 001} and {William Kuszmaul}},
publisher = {IEEE},
booktitle = {63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022}
}
@inproceedings{conf/icalp/0001JM0S22,
title = {Smoothed Analysis of the Komlós Conjecture.},
year = {2022},
booktitle = {ICALP},
author = {{Nikhil Bansal 001} and {Haotian Jiang} and {Raghu Meka} and {Sahil Singla 001} and {Makrand Sinha}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France.}
}
@inproceedings{conf/innovations/BansalJM0S22,
title = {Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing.},
year = {2022},
booktitle = {ITCS},
author = {{Nikhil Bansal 001} and {Haotian Jiang} and {Raghu Meka} and {Sahil Singla 001} and {Makrand Sinha}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA.}
}
@inproceedings{conf/soda/BansalCKPV22,
title = {Learning-Augmented Weighted Paging.},
year = {2022},
booktitle = {SODA},
author = {{Nikhil Bansal 001} and {Christian Coester} and {Ravi Kumar 001} and {Manish Purohit} and {Erik Vee}},
publisher = {SIAM},
booktitle = {Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022}
}
@inproceedings{conf/stoc/0001F22,
title = {The power of two choices in graphical allocation.},
year = {2022},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Ohad N. Feldheim}},
publisher = {ACM},
booktitle = {STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022}
}
@inproceedings{conf/stoc/0001RS22,
title = {Flow time scheduling and prefix Beck-Fiala.},
year = {2022},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Lars Rohwedder} and {Ola Svensson}},
publisher = {ACM},
booktitle = {STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022}
}
@article{journals/corr/abs-2209-08427,
title = {A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem.},
year = {2022},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {John Kuszmaul} and {William Kuszmaul}}
}
@article{journals/talg/ZadehBGNSS22,
title = {Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems.},
year = {2022},
journal = {ACM Trans. Algorithms},
author = {{Sepehr Abbasi Zadeh} and {Nikhil Bansal 001} and {Guru Guruganesh} and {Aleksandar Nikolov} and {Roy Schwartz 002} and {Mohit Singh}}
}
@inproceedings{conf/approx/Ayyadevara0P23,
title = {On Minimizing Generalized Makespan on Unrelated Machines.},
year = {2023},
booktitle = {APPROX/RANDOM},
author = {{Nikhil Ayyadevara} and {Nikhil Bansal 001} and {Milind Prabhu}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA}
}
@inproceedings{conf/stoc/0001JM23,
title = {Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank.},
year = {2023},
booktitle = {STOC},
author = {{Nikhil Bansal 001} and {Haotian Jiang} and {Raghu Meka}},
publisher = {ACM},
booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023}
}
@article{journals/corr/abs-2311-15639,
title = {Almost Logarithmic Approximation for Cutwidth and Pathwidth.},
year = {2023},
journal = {CoRR},
author = {{Nikhil Bansal 001} and {Dor Katzelnick} and {Roy Schwartz 002}}
}
@article{journals/corr/abs-2312-06902,
title = {Perseus: Removing Energy Bloat from Large Model Training.},
year = {2023},
journal = {CoRR},
author = {{Jae-Won Chung} and {Yile Gu} and {Insu Jang} and {Luoxi Meng} and {Nikhil Bansal 001} and {Mosharaf Chowdhury}}
}
@article{journals/eatcs/000123b,
title = {EATCS Distinguished Dissertation Award for 2022.},
year = {2023},
journal = {Bull. EATCS},
author = {{Nikhil Bansal 001}}
}
@article{journals/rsa/BansalH23,
title = {Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture.},
year = {2023},
journal = {Random Struct. Algorithms},
author = {{Nikhil Bansal 001} and {David G. Harris 001}}
}
@article{journals/talg/BansalEKN23,
title = {Competitive Algorithms for Generalized k-Server in Uniform Metrics.},
year = {2023},
month = {January},
journal = {ACM Trans. Algorithms},
author = {{Nikhil Bansal 001} and {Marek Eliás 001} and {Grigorios Koumoutsos} and {Jesper Nederlof}}
}
@article{journals/siamcomp/BansalBFT23,
title = {On Min Sum Vertex Cover and Generalized Min Sum Set Cover.},
year = {2023},
month = {April},
journal = {SIAM J. Comput.},
author = {{Nikhil Bansal 001} and {Jatin Batra} and {Majid Farhadi} and {Prasad Tetali}}
}
@article{journals/ipl/BansalKK23,
title = {A nearly tight lower bound for the d-dimensional cow-path problem.},
year = {2023},
month = {August},
journal = {Inf. Process. Lett.},
author = {{Nikhil Bansal 001} and {John Kuszmaul} and {William Kuszmaul}}
}