Conference paper
A tale of two dimensional bin packing
Nikhil Bansal, Andrea Lodi, et al.
FOCS 2005
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, Andrea Lodi, et al.
FOCS 2005
Maurice Queyranne, Maxim Sviridenko
Journal of Algorithms
Jon Lee, Maxim Sviridenko, et al.
SIAM Journal on Computing
Nikhil Bansal, Maxim Sviridenko
Discrete Optimization