CATS-May-6-2016
Title[edit]
Survey: Randomized Dependent Rounding of Linear Programs
Speaker[edit]
Karthik A Sankararaman
Abstract[edit]
In this talk, we survey some of the techniques for doing dependent randomized rounding of LPs. The goal of such dependent randomized rounding is to get concentration of some linear function of the variables around its mean, while maintaining the marginals as much as possible.
We first start with the GKPS algorithm[1] for Bipartite graphs. We then briefly describe the Maximum-Entropy Sampling technique used in the context of Spanning Trees(This was explained in full detail by Ahmed couple of talks ago)[2]. We finally describe the generalization of the above two techniques, given by Chekrui et al.[3]
[1] http://www.cs.umd.edu/~srin/PS/2006/depround-jou.ps
[2] http://homes.cs.washington.edu/~shayan/atsp.pdf
[3] Dependent Randomized Rounding for Matroid Polytopes (http://arxiv.org/abs/0909.4348)
