# Iterative Partial Rounding for Vertex Cover with Hard Capacities

## Abstract

We provide a simple and novel algorithmic design technique, for which we call iterative partial rounding, that gives a tight rounding-based approximation for vertex cover with hard capacities (VC-HC). In particular, we obtain an f-approximation for VC-HC on hypergraphs, improving over a previous results of Cheung et al. (In: SODA’14, 2014) to the tight extent. This also closes the gap of approximation since it was posted by Chuzhoy and Naor (Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS) 2002, pp. 481--489. IEEE Computer Society, 2002). Our main technical tool for establishing the approximation guarantee is a separation lemma that certifies the existence of a strong partition for solutions that are basic feasible in an extended version of the natural LP. We believe that our rounding technique is of independent interest when hard constraints are considered.

This is a preview of subscription content, access via your institution.

1. An augmented $$(\alpha ,\beta )$$-covering is a solution that violates the multiplicity limit by a factor $$\alpha$$ and has a cost factor $$\beta$$ to the optimal LP solution for VC-HC.

2. Recall that $$p \in {\mathbf {Q}}(\Psi )$$ is an extreme point if it is not in the interior of any line segment contained in $${\mathbf {Q}}(\Psi )$$, i.e., $$p = \lambda r + (1-\lambda ) s$$ for some $$0< \lambda < 1$$ implies that either $$r \notin {\mathbf {Q}}(\Psi )$$ or $$s \notin {\mathbf {Q}}(\Psi )$$.

3. Note that, in Equation (6) we also drop out $$h_{e,v}$$ for all $$e \in {\mathcal C}^{(E)}$$ and $$v \in e {\setminus } e^{{\text {actv}}}_h$$ since by definition they are zero at the considered extreme point p.

4. If not, the column reduction (Gaussian elimination on the columns) would have led to a rank less than $$\left| X \cup H^*\right|$$, a contradiction to the fact that $$\tilde{M}$$ has a full column rank.

## References

1. An, H.-C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated $$k$$-center. Math. Program. 154(1–2), 29–53 (2015)

2. An, H.-C., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. SIAM J. Comput. 46(1), 272–306 (2017)

3. Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: ESA’12, pp. 133–144 (2012)

4. Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981)

5. Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$-median, and positive correlation in budgeted optimization. ACM Trans. Algorithms 13(2), 23:1–23:31 (2017)

6. Cheung, W.-C., Goemans, M., Wong, S.: Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: SODA’14 (2014)

7. Chuzhoy, J., Naor, J.: Covering problems with hard capacities. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS) 2002, 16–19 November 2002, Vancouver, BC, Canada, pp. 481–489. IEEE Computer Society (2002). https://doi.org/10.1109/SFCS.2002.1181972

8. Chuzhoy, J., Naor, J.: Covering problems with hard capacities. SIAM J. Comput. 36(2), 498–515 (2006)

9. Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated domination faster than O($$2^n$$). Inf. Process. Lett 111((23–24)), 1099–1103 (2011)

10. Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: IWPEC’08, pp. 78–90 (2008)

11. Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci. 72, 16–33 (2006)

12. Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324–360 (2006)

13. Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004)

14. Grandoni, F., Könemann, J., Panconesi, A., Sozio, M.: A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM J. Comput. 38(3), 825–840 (2008)

15. Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering. J. Algorithms 48(1), 257–270 (2003)

16. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms 31(1), 228–248 (1999)

17. Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555–556 (1982)

18. Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$-center problem. Math. Oper. Res. 10(2), 180–184 (1985)

19. Kao, M.-J., Chen, H.-L., Lee, D.T.: Capacitated domination: problem complexity and approximation algorithms. Algorithmica 72, 1–43 (2015)

20. Kao, M.-J., Liao, C.-S., Lee, D.T.: Algorithmica. Capacitated domination problem 60(2), 274–300 (2011)

21. Kao, M.-J., Tu, H.-L., Lee, D.T.: An O($$f$$) bi-approximation for weighted capacitated covering with hard capacities. Algorithmica 81(5), 1800–1817 (2019)

22. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\epsilon$$. J. Comput. Syst. Sci. 74(3), 335–349 (2008)

23. Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45–58 (2013)

24. Li, S.: On uniform capacitated $$k$$-median beyond the natural lp relaxation. ACM Trans. Algorithms 13(2), 22:1–22:18 (2017)

25. Li, S., Svensson, O.: Approximating $$k$$-median via pseudo-approximation. SIAM J. Comput. 45(2), 530–547 (2016)

26. Liedloff, M., Todinca, I., Villanger, Y.: Solving capacitated dominating set by using covering by subsets and maximum matching. Discret. Appl. Math. 168, 60–68 (2014)

27. Saha, B., Khuller, S.: Set cover revisited: hypergraph cover with hard capacities. In: ICALP’12, pp. 762–773 (2012)

28. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)

29. Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385–393 (1982)

## Acknowledgements

The author would like to thank Kai-Min Chung, Herbert Yu, and the anonymous reviewers for their valuable comments on the presentation of this work.

## Author information

Authors

### Corresponding author

Correspondence to Mong-Jen Kao.
{"ft_lang_label":"__label__en","ft_lang_prob":0.7302089,"math_prob":0.9676558,"size":7054,"snap":"2023-40-2023-50","text_gpt3_token_len":2130,"char_repetition_ratio":0.12978724,"word_repetition_ratio":0.030907279,"special_character_ratio":0.3328608,"punctuation_ratio":0.27816236,"nsfw_num_words":3,"has_unicode_error":false,"math_prob_llama3":0.98651767,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-05T08:58:48Z\",\"WARC-Record-ID\":\"<urn:uuid:901f8ca8-d233-4ff2-a564-c6838a8e9445>\",\"Content-Length\":\"237251\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b89d17b6-c074-4295-bea2-0e579ce241d2>\",\"WARC-Concurrent-To\":\"<urn:uuid:786cd0f1-4b47-4f7a-a783-2178b8c4eb2c>\",\"WARC-IP-Address\":\"146.75.32.95\",\"WARC-Target-URI\":\"https://link.springer.com/article/10.1007/s00453-020-00749-9?error=cookies_not_supported&code=49189a8a-e35f-419b-acbe-bb9d7c2fda14\",\"WARC-Payload-Digest\":\"sha1:R6ARHQDGBH3NPRFBNRRFFYSPZKVYWSFA\",\"WARC-Block-Digest\":\"sha1:Y2Q6OXQZY2P2SMJJUM3HT4FT67PIMHP7\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100550.40_warc_CC-MAIN-20231205073336-20231205103336-00758.warc.gz\"}"}