Publications

Publications  (in reverse chronological order):  

(please email me for a copy if you do not see an online version of a paper here)

• A Structural Lemma in 2-Dimensional Packing, and its Implications on Approximability. Nikhil Bansal, Alberto Caprara and Maxim Sviridenko.
  
  
• Improved bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs and Dmitriy Rogozhnikov-Katz.
  
  
• Towards Optimal Operator Placement in Partial-Fault Tolerant Applications. Nikhil Bansal, Ranjita Bhagwan, Navendu Jain, Yoonho Park, Deepak Turaga, Chitra Venkataramani and Olivier Verscheure. In INFOCOM 2008.
  
  
• Additive Guarantees for Degree Bounded Direct Network Design . Nikhil Bansal, Rohit Khandekar and Viswanath Nagarajan. In STOC 2008.
  
      Suppose you want to compute a minimum cost spanning tree of a graph but are given degree bounds on each vertex. In a recent breakthrough result, Singh and Lau showed that such a tree can be found with degree violation of at most +1 at each vertex. Their proof is based on an elegant use of the iterated rounding technique first introduced by Jain. We are interested in the directed version of this question (consider for example the problem of computing a minimum cost rooted arborescence subject to degree bounds). We show that for any epsilon between 0 and 1/2, we can compute a solution with degrees at b_v/(1-\epsilon) +O(1) and cost 1/\epsilon time optimum. This improves previous guarantees due to Singh et al. Somewhat surprisingly, there is an integrality gap instance that shows that this tradeoff cannot be improved. The result is surprising simple, and the key is a new counting argument. Based on this counting argument we also give an extremely simple proof of the +1 guarantee of Singh and Lau for min cost MST problem.
  
  
• Randomized Competitive Algorithms for Generalized Caching . Nikhil Bansal, Niv Buchbinder and Joseph (Seffi) Naor. In STOC 2008.
  
      The generalized caching problem is a generalization of the classic paging problem where pages can arbitrary sizes and arbitrary weights. We give the first polylogarithmic competitive algorithm for the problem. Our algorithm is O(log^2 k) competitive. The algorithm is again based on the primal dual framework for online algorithms, but we need several new technical ideas. Especially, we need to work with a substantially stronger LP formulation where exponentially many constraints are added at each time step.
  
  
• Average Rate Speed Scaling . Nikhil Bansal, David Bunde, Ho-Leung Chan and Kirk Pruhs. In LATIN 2008
  
      The Average rate algorithm (AVR) for deadline feasibility with speed scaling was proposed in their seminal paper by Yao, Demers and Shenker. They showed that it is 2^{alpha-1} alpha^\alpha competitive, where alpha is power to speed exponent. They conjectured that the right competitive is \alpha^\alpha. In this paper we give an instance where AVR is actually (2-\epsilon)^\alpha \alpha^\alpha competitive, where \epsilon tends to zero as \alpha gets larger. We also give a substantially simpler and elementary potential function based proof of the 2^{\alpha-1} \alpha^\alpha competitiveness of AVR.
  
  
• "Scheduling for speed bounded processors . Nikhil Bansal, Ho-Leung Chan, Tak-Wah Lam and Lap-Kei Lee, in ICALP 08.
  
      We consider speed scaling algorithms when the maximum processor speed is bounded. We give essentially optimum results for throughput maximization and minimizing flow time plus energy.
  
  
• Non-Preemptive min-sum scheduling with resource augmentation . Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber and Cliff Stein, in FOCS 2007.
  
      We give an O(1)-speed, O(1)-approximation for minimizing total flow time non-preemptively on a single machine. Without speed up, a hardness of o(n^1/2) is known, and prior O(1) approximation algorithms required logarithmic speedup. The key idea is to add certain penalty terms to the time indexed LP that capture non-preemptiveness. We also consider other variants such as tardiness and throughput maximization.
  
  
• A primal-dual randomized algorithm for weighted paging . Nikhil Bansal, Niv Buchbinder and Joseph (Seffi) Naor, in FOCS 2007.
  
      We give an O(log k) competitive randomized algorithm for the weighted paging problem, where the pages have arbitrary fetching costs. This generalizes the well known Randomized Marking algorithm that works for uniform weights. An interesting aspect of our result is that it is substantially simpler than the previous approaches for the problem, and is based on the primal dual framework for online problems developed by Buchbinder and Naor.
  
  
• An O(log^2 k) competitive algorithm for metric bipartite matching , Nikhil Bansal, Niv Buchbinder, Anupam Gupta and Joseph (Seffi) Naor, in ESA 2007.
  
      We give an O(log^2 k) competitive randomized algorithm for the metric bipartite matching problem improving upon the recent O(log^3 k) competitive algorithm of Meyerson et al. in SODA 06.
  
  
• A classical approximation scheme for the ground-state energy of Ising spin Hamiltonians on planar graphs, Nikhil Bansal, Sergey Bravyi and Barbara M. Terhal. The quant-ph arxiv version
  
      We give a polynomial time approximation scheme for the Ising problem with an external magnetic field on a planar graph. Our algorithms are reasonably efficient with running times of 2^{O(1/eps)} n.
  
  
• Competitive algorithms for due date scheduling, Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs. ICALP 2007.
  
      We consider a scheduling model motivated by make-to-order manufacturing. Here the customer places an order for a product and the company must quote a due date by which the order must be completed. The quote must be made at the moment the order is made without the knowledge of the future. A large due date would mean a low profit or losing the customer all together, while quoting a small due date would leave us inflexible in case more profitable jobs arrive in the near future. We consider two variants of the problem and give algorithms with essentially optimum competitive ratios.
  
  
• Robust Reductions from Ranking to Classification, Maria-Florina Blacan, N. Bansal, A. Beygelzimer, D. Coppersmith, J. Langford and G. Sorkin. COLT 2007.
  Journal version , invited to Machine Learning, special issue for COLT 07 papers.
  
      We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r.
  
  
• Dynamic Pricing for Impatient Bidders, N. Bansal, N. Chen, N. Cherniavsky, A. Rudra, B. Schieber and M. Sviridenko. SODA 2007.
  Journal Version , to appear in Transaction on Algorithms.
  
      We consider the envy free pricing model where each user is interested in an item during a time interval s_i,t_i and is willing to pay up to b_i. Given a setting on prices the user buys the item at least price during s_i, t_i, provided this price is below b_i. We consider online algorithms to set prices to maximize total profit. Our main result is an sqrt{log h/log log h} lower bound on the competitive ratio of any randomized algorithm, where h is max to min price ratio. Note that an O( log h) randomized algorithm follows trivially by initially choosing a random price among 1,2,4...,h/2,h and fixing it forever.
  We also consider the "impatient" model, where the user buys the item at the first time when price is below b_i. We give a O(log log h) randomized algorithm and show a lower bound of sqrt{log log n/log log log h}. We also give upper and lower bounds for deterministic algorithms.
  
  
• Harmonic Algorithm for 3-Dimensional Strip Packing Problem . N. Bansal and M. Sviridenko (to be merged with a paper by X. Han, K. Iwama and G. Zhang who independently obtained similar results) in SODA 2007.
  Journal Version , submitted.
  
      We consider the 3D strip packing problem and give an 1.69+eps approximation, improving upon the previous 2+eps approximation due to Jansen and Zhang. The algorithm uses a simple connection between bin packing and strip packing. As a side result, we also give a very simple proof of 1.69+eps approximation for 2D bin packing due to Caprara 2002.
  
  
• Speed Scaling for Weighted Flow time , N. Bansal, K. Pruhs and C. Stein , in SODA 2007.
  
      We consider the speed scaling setting and study algorithms for minimizing flow time plus energy of a processor. We give a 4 competitive algorithm for unit size unweighted jobs, and an O(alpha^2/\ln^2 alpha) competitive algorithm for arbitrary size weighted jobs, where alpha is the speed scaling exponent.
  
  
• On the Longest Common Rigid Subsequence Problem , N. Bansal, M. Lewenstein, B. Ma, K. Zhang, to appear in Algorithmica.
  
      We consider the longest common rigid subsequence problem first defined by Ma and Zhang in CPM 05. We show that it cannot be approximated to within n^delta for some delta>0 where n is the length of the strings, and to within o(m) where m is the number of strings.
  
  
• Improved approximation algorithms for multidimensional bin packing problems ,   N. Bansal, A. Caprara, M. Sviridenko. FOCS 2006
  
     We introduce the notion of subset oblivious algorithms and show how they are useful for approximating bin packing type problems. Given a subset oblivious algorithm with approximation ratio rho, our algorithm gives a 1+ \ln rho approximation. We use this to obtain a 1 + \ln 1.69 = 1.52 approximation for 2-d packing with and without rotations and a 1+\ln d approximation for d-dimensional vector packing.
  
  
• The Santa Claus Problem ,   N. Bansal, M. Sviridenko. STOC 2006
  Journal version .
  
      We consider the Santa Claus problem where there are k kids and n items and kid i has utility p_ij for item j. The overall utility of a kid is the sum of all items assigned to it and the goal is to maximize the minimum utility of all kids. We give an O(log log k/log log log k) approximation for the restricted assignment case, where p_ij \in {p_j,0} (i.e. for each item j, some subset S_j of kids care for it and have value p_j and rest have value 0). The guarantee is based on rounding a certain natural exponential sized configuration LP. We also show an integrality gap of k^{1/2} for the general case.
  
  Update: Recently, Asadpour and Saberi give a k^{1/2} log^3 k approximation for the general case. For the restricted assignment case, Feige has recently shown a non-constructive O(1) integrality gap for the configuration LP.
  
  
• A Quasi-PTAS for unsplittable flow on line graphs ,  N. Bansal, A. Chakrabarti, A. Epstein, B. Schieber. STOC 2006
  
      We study the Unsplittable Flow Problem (ufp) on line graphs and cycles. We describe a deterministic quasi-polynomial time approximation scheme thereby ruling out an APX-hardness result. Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. Earlier results on this problem included a polynomial time (2+eps)-approximation under the assumption that no demand exceeds any edge capacity (the ``no-bottleneck assumption'') and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on ufp, our results do not require a no-bottleneck assumption.
  
  
• Minimizing Setup and Beam-On times in Radiation Therapy ,   N. Bansal, D. Coppersmith, B. Schieber. APPROX 2006
  


• Improved Approximation Algorithms for broadcast Scheduling,   N. Bansal, D. Coppersmith and M. Sviridenko,  in Symposium on Discrete Algorithms, SODA 06. Journal version
  
      We give an O(log^2 n/log log n) approximation for minimizing the average response time for broadcast scheduling problem. This improves upon the previous O(n^{1/2}) approximation.
  
  Errata: Unfortunately, the claimed 5/6 approximation for the throughput maximization version of the problem has an error. The best result for this problem is still the 3/4 approximation due to Gandhi, Khuller, Parthasarty and Srinivasan.
  
  
• A Tale of Two Dimensional Bin Packing,  N. Bansal, A. Lodi and M. Sviridenko, in Foundations of Computer  Science, FOCS 2005, 657-666.
  
      We give an approximation scheme for the 2D guillotine bin packing problem. A packing is called guillotine if each item can be obtained from the packing by applying a sequence of edge to edge parallel cuts to the bin. This is somewhat surprising since 2D bin packing (without the guillotine constraint) is APX Hard. Guillotine packings are very desirable in practice for cutting stock problems.
  
  
• Speed scaling to manage temperature, N. Bansal and Kirk Pruhs, STACS 2005, 460-471.
  
      We consider the problem of minimizing the maximum temperature online in speed scaling model and give an O(1) competitive algorithm.
  
  
• Approximation the Average Response Time in Broadcast Scheduling, N. Bansal, M. Charikar, S. Khanna and J. Naor, in
  Symposium on Discrete Algorithms, SODA 2005, 215-221.
  
      We consider the problem of minimizing the average response time in broadcast scheduling setting. We give the first sublinear O(n^{1/2}) approximation, and an (1+eps)-speed, O(1/eps) approximation. This result has been improved in the BCS06 paper above.
  
  
  
• Jobshop scheduling with unit processing times, N. Bansal, T. Kimbrel and M. Sviridenko, in Symposium on Discrete Algorithms, SODA 2005, 207-214. Journal version in Math of Operations Research, Vol 31(2), 381-389, 2006.
  


• Dynamic Speed Scaling to manage energy and temperature,  N. Bansal, T. Kimbrel and K. Pruhs, in Foundations of Computer  Science, FOCS 2004, 520-529. The journal version of this paper combines results with the STACS 05 paper above. Journal of the ACM, Vol 51, issue 1, March 2007.
  
      We consider the speed scaling model introduced by Yao, Demers and Shenker 95 motivated by dynamic voltage scaling technology in modern processors, where the processor can run arbitrarily fast, but uses energy at rate s^alpha at speed s. Given a collection of jobs with arbitrary release times, deadlines and sizes the goal is to finish them all with minimum energy usage. We give a tight analysis of OA, an algorithm proposed by YDS95, and another almost optimum algorithm with competitive ratio about 2 e^\alpha+1. We also consider the problem of minimizing the maximum speed, and give an offline algorithm for minimizing the maximum temperature where the dynamics of temperature is determined by Fourier's law of cooling.
  
  
• Further Improvements in Competitive Guarantees for QoS Buffering,  M. Mahdian, N. Bansal, L. Fleischer, T. Kimbrel, B. Schieber, M. Sviridenko,   in International Colloquium on Automata, Languages and Programming, ICALP 2004, 196-207.
  


• Efficient algorithms for finding submasses in weighted strings, N. Bansal, M. Cieliebak and Z. Liptak, in Combinatorial Pattern Matching, CPM 2004, 194-204. Journal version appears as Finding submasses in weighted strings using Fast Fourier Transform, in Discrete Applied Mathematics 155 (2007) 707-781.
  
      We consider several variants of the following problem: Given a string with weighted alphabets and a mass M find substring(s) with weight M. We give fast algorithms for these problem based on a combination of fast fourier transforms and random sampling.
  
  
• One dimensional resource augmentation in 2D bin packing, N. Bansal and M. Sviridenko, to appear in Journal of Discrete optimization.
  
      We show that the 2D bin packing admits an approximation scheme if we relax the size of the bins to (1+eps x 1).
  
  
• Minimizing makespan in no-wait job shops, N. Bansal, M. Mahdian and M. Sviridenko,   Mathematics of Operations Research v.30 (2005), pp. 817-831.
  
      We settle the approximability of minimizing the makespan for no-wait job shop scheduling. It was known that the problem is MaxSNP-hard when each job is allowed to have three operations or more. If each job has at most two operations, we show that the problem admits a PTAS for m=O(1) machines, and is hard to approximate within a factor better than 5/4 when m is part of the input.
  
  
• Achievable sojourn times by non-size based policies in a GI/GI/1 queue, Nikhil Bansal, submitted for publication.
  
      We show how Yao's Minimax Lemma that is commonly used to lower bound the competitive ratio for randomized algorithm can be used to show the existence of scheduling policies that do not use the knowledge of job sizes and yet have average sojourn essentially that of the optimum SRPT. In particular we show that, under very general conditions, there always exists a policy that does not use the knowledge of sizes and yet its average sojourn time is no more than O(log (1/1-\rho)) times that of SRPT.
  
  
• Handling load with less stress, Nikhil Bansal and David Gamarnik, in Queueing Systems: Theory and Applications, 54(1), 45-54, 2006.
  
      We consider M/G/1 queues where the job sizes have a Pareto distribution. We show that for certain parameters, the average sojourn time under SRPT and FB varies as 1/log (1/(1-\rho)) with load \rho. This is exponentially better than policies like Processor Sharing where it varies as 1/(1-\rho). This is particularly surprising as FB does not require the knowledge of job sizes. We then investigate this behavior for other distributions, and compare the effect of knowledge of jobs sizes, and partial knowledge of job sizes.
  
  
• On the average sojourn time under M/M/1/SRPT, Nikhil Bansal, Operations Research Letters, Volume 33, 2, March 2005, 195-200.
  
      We show that the average sojourn time in M/M/1 queue under Shortest Remaining time policy varies is (1+o(1)) / (\mu (1-\rho) log (e/(1-\rho))) as a function of the load \rho. This implies a non-constant gap between SRPT and policies such as FIFO, PS or FB all of which have a sojourn time of 1/\mu (1-\rho).
  
  
• Approximation Agorithms for Deadline-TSP and Vehicle Routing  with Time-Windows, Nikhil Bansal, Avrim Blum, Shuchi Chawla and Adam Meyerson,  in Symposium on Theory of Computing, STOC 2004, 166-174.
  
      In the deadline TSP problem, each vertex has a deadline, and given a start vertex r, the goal is to visit as many vertices as possible before their deadlines (we get no credit for visiting a vertex after its deadline). We give a log n approximation for the problem. We also extend it to the say when vertices has time windows and give an O(min(log^2 n, log D_max)) approximation.
  
  
• Server Scheduling in the Weighted l_p Norm , Nikhil Bansal and Kirk Pruhs, in LATIN 2004, 434-443.
  


• A Note on Comparing Response Times in the M/GI/1/FB and M/GI/1/PS Queues,Nikhil Bansal, Adam Wierman and Mor Harchol-Balter, in Operations Research Letters, 32(1), January 2004, 73-76.


• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes , N. Bansal, J. Correa, C. Kenyon and M. Sviridenko, Mathematics of Operations Research v.31 (2006), pp. 31-49. This paper is a union of two papers "Approximation Schemes for Multidimensional Packing" and "New approximability and inapproximability results for 2-dimensional bin packing", in Proceedings of SODA 2004, pp.179--188 and pp.189--196.
  
      We show that no asymptotic PTAS exists for the 2D bin packing problem. We give an asymptotic PTAS for the case of packing squares, and for the easier problem of packing rectangles in to bins of size (1+eps x 1+eps).
  
  
• On minimizing the total Flow Time on Multiple Machines, Nikhil Bansal, in Symposium on Discrete Algorithms,  SODA 2004,  565-567.
  Journal version in Operations Research Letters, 33(3), 267-273
  
      We give a QPTAS for minizing average flow time on O(1) machines. It is open to obtain a polynomial time algorithm with a sublogarithmic approximation ratio even for the case of 2 machines. Our result suggests that a PTAS is likely.
  
  
• Analysis of Processor Sharing with Bulk Arrivals, Nikhil Bansal in Operations Research Letters, 31(5), September 2003, 401-405.
  


• Online Oblivious Routing, Nikhil Bansal, Avrim Blum, Shuchi Chawla and Adam Meyerson, Symposium on Parallel Algorithms and Architectures, SPAA 2003, pages 44-49.


• Scheduling For Flow-Time with Admission Control (or, How to manage your  to-do list) Nikhil Bansal, Avrim Blum, Shuchi Chawla and Kedar Dhamdhere, European Symposium on Algorithms, ESA 2003, pages 43-54.


•  Server Scheduling in the L_p Norm: A Rising Tide Lifts All Boats, Nikhil Bansal  and  Kirk Pruhs, in Symposium on Theory of Computing,   STOC 2003, pages 242-250.
  Journal version: Server scheduling to balanace priorities, fairness and average quality of service.
  
      We consider algorithms to minimize the ell_p norms of flow time or slowdown. The motivation is that such algorithms are likely to be both good with respect to average performance and worst case performance.
  
  
• Capacity, Mobility and Delay in Wireless Ad hoc Networks, Nikhil Bansal and Zhen Li, in INFOCOM 03.


• Improving web Performance in Broadcast-Unicast Networks, Mukesh Agrawal, Amit Manjhi, Nikhil Bansal and Srinivasan Seshan, in INFOCOM 03.


• Minimizing Weighted Response Time, Nikhil Bansal  and Kedar Dhamdhere, in Symposium on Discrete Algorithms, SODA (2003),  pages 508-516.
  Journal version in Transactions of Algorithms (TALG), special issue for SODA 03 papers.
  
      We give an O(log W) competitive algorithm for minimizing the weighted flow time on a single machine, where W is the max to min weight ratio.
  
  
• Size based Scheduling to improve web performance, Mor Harchol-Balter, Bianca  Schroeder, Nikhil Bansal  and Mukesh   Agarwal, in Transactions on Computer Systems, May 2003, 21(2), 207-233


• Non-Clairvoyant Scheduling for Mean Slowdown,  Nikhil Bansal, Kedar Dhamdhere, Jochen Konemann and Amitabh Sinha, Proc. of the 20th Intl. Symposium on Theoretical Aspectes of Computer Science  (STACS 2003), pages 260-270.   Journal version in Algorithmica 2004, 40, 305-318.
  
      The slowdown (aka normalized response time) of a job is its response time divided by its size. Motivated by applications in operating systems we consider the problem of minimizing the average slowdown in the non-clairvoyant setting, where the size of a job is revealed to the scheduler only when the job meets its service requirement and terminates.
  
  
• Correlation Clustering, Nikhil Bansal,  Avrim Blum and Shuchi Chawla, 43rd Symposium on Foundations of Computer Science ( FOCS 2002),  pages 238-247.   Journal version appears in  Machine Learning Journal, special Issue: Theoretical Advances in Data Clustering (Guest Editors: Nina Mishra and Rajeev Motwani), 56 (1-3): 89-113.
  
      Suppose we are given n documents and a complete graph where each edges are labelled + or - depending on whether the documents are similar or dissimilar. Suppose these edge labels are not perfect (have some error), how do we find a clustering of documents that agrees with the labelling as much as possible?
  
  Update: These results have been improved and extended by the work of Charikar & Wirth, Demaine & Immorlica, Emanuel & Fiat and other later works.
  
  
• Bin-packing with Fragile Objects , Nikhil Bansal, Zhen Liu and Arvind Sankar, 2nd IFIP  Intl. Conf. on Theoretical Computer Science 02, pages 38-46.
  Journal Version to appear in Wireless Networks.
  
      We are given items with two attributes: weight and fragility. A subset is said to be packed feasibly in a bin if the total weight of items is no more than the fragility of any item in that bin. Find the packing with least number of bins. Note that if all fragilities are 1, this reduces to traditional bin packing. The problem is motivated by channel assignment problem in CDMA wireless networks.
  
  
• Approximate Analysis of M/G/1/PS and M/G/1/SRPT under Transient Overload ,  with Mor Harchol-Balter (preliminary work   appeared in (MAMA 2001), also as Performance Evaluation Review  Vol 29, 3, December 2001)


• Analysis of SRPT Scheduling: Investigating Unfairness , Nikhil Bansal and  Mor Harchol-Balter, In  ACM SIGMETRICS/PERFORMANCE 2001 , pages 279-290
  
      The Shortest Remaining Processing Time (SRPT) is optimum for minimizing average response time, but is this improvement on average caused by penalizing long jobs disproportionately? We compare SRPT with Processor Sharing (PS) in an M/G/1 setting. Interestingly, in fairly general settings, it turns out that for every sized job, both long and short, average sojourn time under SRPT is less than that under PS.
  
  
• SRPT scheduling for Web Servers , Mor Harchol-Balter, Nikhil Bansal, Bianca Schroeder and Mukesh Agarwal, In Job Scheduling Strategies for Parallel Processing, JSSPP 2001, pages 11-20


• Upper Bounds for MaxSat: Further Improved, Nikhil Bansal and Venkatesh Raman, In  10th International Symposium, ISAAC 1999, pages 247-258.
  
  
• An Identity for Strongly ConnectedDigraphs, Nikhil Bansal, American Mathematical Monthly, Nov. 1999