Conference paper
The Santa Claus problem
Nikhil Bansal, Maxim Sviridenko
STOC 2006
In this work we propose new randomized rounding algorithms for matroid intersection and matroid base polytopes. We prove concentration inequalities for polynomial objective functions and constraints that has numerous applications and can be used in approximation algorithms for Minimum Quadratic Spanning Tree, Unrelated Parallel Machines Scheduling and scheduling with time windows and nonlinear objectives. We also show applications related to Constraint Satisfaction and dense polynomial optimization.
Nikhil Bansal, Maxim Sviridenko
STOC 2006
Carlile Lavor, Jon Lee, et al.
Optimization Letters
Viswanath Nagarajan, Maxim Sviridenko
SODA 2009
Alexander Ageev, Refael Hassin, et al.
SIAM Journal on Discrete Mathematics