Changes

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.

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 Pipage rounding(which is deterministic) and then describe 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]

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]