<p>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.</p>

<p><a href="https://arxiv.org/abs/1811.01597" rel="nofollow noreferrer">https://arxiv.org/abs/1811.01597</a> by Nikhil Bansal unifying iterated and dependent rounding.</p>

CC BY-SA 4.0
2020-05-08T18:37:49.667Z
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?
Mengfan Ma
CC BY-SA 4.0
2020-05-07T22:02:13.017Z
2020-05-07T22:02:13.017Z
Chandra Chekuri
<p>I'm seeking for materials on dependent rounding. However, what I've found are two papers:</p>

<ul>
<li>Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A., 2006. Dependent rounding and its applications to approximation algorithms. J. ACM</li>
<li>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</li>
</ul>

<p>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. <strong>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</strong>. (I think)There should be other dependent rounding procedures with other nice properties. My question is:</p>

<ol>
<li>How can I find dependent rounding procedures with the desirable properties when designing  approximation algorithms? </li>
<li>Are there tuitorial-level materials on how to use dependent rounding to design approximation algorithms?</li>
</ol>

<reference-request><approximation-algorithms>
How can I find dependent rounding procedures with the desirable properties?
Mengfan Ma
# How can I find dependent rounding procedures with the desirable properties?

(Asked by: username_0 on 2020-05-07)

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?

**Tags:** reference-request, approximation-algorithms


---

## 1 answers

### Answer by username_1 on 2020-05-07. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  

---

