1
$\begingroup$

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?
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I looked at your listed paper briefly, may I conclude that the sub-isotropic rounding in this paper has no hope to improve the existing approximation algorithms using dependent randomized rounding? $\endgroup$
    – Mengfan Ma
    May 8 '20 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.