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:
- How can I find dependent rounding procedures with the desirable properties when designing approximation algorithms?
- Are there tuitorial-level materials on how to use dependent rounding to design approximation algorithms?