38 citations · 157 across the 44 of their papers we have counts for
4 papers · 1 filter
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh +3
Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rou…
On a generalization of iterated and randomized rounding
Nikhil Bansal
We give a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever ite…
On the discrepancy of random low degree set systems
Nikhil Bansal, Raghu Meka
Motivated by the celebrated Beck-Fiala conjecture, we consider the random setting where there are elements and sets and each element lies in randomly chosen sets. In th…
Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems
Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty +1
In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling…