38 citations · 157 across the 44 of their papers we have counts for
Showing 2015 · cs.DSShow all
3 papers · 2 filters
cs.DS2015★ 3 cited
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…
cs.DS2015
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…
cs.DS2015★ 7 cited
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…