How can I find dependent rounding procedures with the desirable properties?

Question

I'm seeking for materials on dependent rounding. However, what I've found are two papers:

• Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A., 2006. Dependent rounding and its applications to approximation algorithms. J. ACM
• Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K., 2015. An Improved Approximation for K-Median, and Positive Correlation in Budgeted Optimization. SODA ’15

The first one can be used to deal with problems with hard cardinality constraints, while the second one can be used to deal with weighed constraints. I'd like to use dependent rounding as a tool to design (approximation) algorithms and I'm not interested in the mechanism behind the specific dependent rounding procedure. (I think)There should be other dependent rounding procedures with other nice properties. My question is:

1. How can I find dependent rounding procedures with the desirable properties when designing approximation algorithms?
2. Are there tuitorial-level materials on how to use dependent rounding to design approximation algorithms?

Answer 1

Dependent randomized rounding is a broad tool that is used in many approximation algorithms. Lot depends on the problem structure, objective and constraints and there is no single unified answer/framework. Some papers like the ones you mention identify generic settings where one has some nice probabilistic tools and provide some applications. I list a paper below that provides a more general framework and also has pointers to other work on dependent rounding. I also recommend looking at approximation algorithms books such as the ones by Williamson and Shmoys, and Vazirani to see the variety of dependent rounding schemes that are used.

https://arxiv.org/abs/1811.01597 by Nikhil Bansal unifying iterated and dependent rounding.