38 citations · 157 across the 44 of their papers we have counts for
4 papers · 1 filter
Achievable Performance of Blind Policies in Heavy Traffic
Nikhil Bansal, Bart Kamphorst, Bert Zwart
For a GI/GI/1 queue, we show that the average sojourn time under the (blind) Randomized Multilevel Feedback algorithm is no worse than that under the Shortest Remaining Processing…
Approximation-Friendly Discrepancy Rounding
Nikhil Bansal, Viswanath Nagarajan
Rounding linear programs using techniques from discrepancy is a recent approach that has been very successful in certain settings. However this method also has some limitations whe…
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan, Ola Svensson
We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a -approximation algorithm for…
On the Lovász Theta function for Independent Sets in Sparse Graphs
Nikhil Bansal, Anupam Gupta, Guru Guruganesh
We consider the maximum independent set problem on graphs with maximum degree~. We show that the integrality gap of the Lovász -function based SDP is $\widetilde{O}(d…