Conference paper
Integrality gaps for sherali-adams relaxations
Moses Charikar, Konstantin Makarychev, et al.
STOC 2009
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.
Moses Charikar, Konstantin Makarychev, et al.
STOC 2009
T.S. Jayram, Tracy Kimbrel, et al.
STOC 2001
Guojing Cong, Konstantin Makarychev
IPDPS 2011
Konstantin Makarychev, Warren Schudy, et al.
SODA 2012