{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:00:56Z","timestamp":1783576856865,"version":"3.55.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,11]],"date-time":"2021-04-11T00:00:00Z","timestamp":1618099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,11]],"date-time":"2021-04-11T00:00:00Z","timestamp":1618099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,3]]},"abstract":"Abstract<\/jats:title>We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f<\/jats:italic>. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f<\/jats:italic>. The approximation factor of our algorithm is $$(f+\\varepsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n f<\/mml:mi>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Let $$\\varDelta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denote the maximum degree in the hypergraph. Our algorithm runs in the congest<\/jats:sc> model and requires $$O(\\log {\\varDelta } \/ \\log \\log \\varDelta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds, for constants $$\\varepsilon \\in (0,1]$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n \u2208<\/mml:mo>\n (<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$f\\in {\\mathbb {N}}^+$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \u2208<\/mml:mo>\n \n \n N<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal<\/jats:italic> distributed algorithms. For constant values of f<\/jats:italic> and $$\\varepsilon $$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, our algorithm improves over the $$(f+\\varepsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n f<\/mml:mi>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is $$O(\\log \\varDelta + \\log W)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n +<\/mml:mo>\n log<\/mml:mo>\n W<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where W<\/jats:italic> is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f<\/jats:italic>-approximation for the problem in $$O(f\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n f<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds, improving over the classical result of Khuller et al. (J Algorithms, 1994) that achieves a running time of $$O(f\\log ^2 n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n f<\/mml:mi>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, for weighted vertex cover ($$f=2$$<\/jats:tex-math>\n \n f<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) our algorithm achieves a deterministic<\/jats:italic> running time of $$O(\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, matching the randomized<\/jats:italic> previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an $$(f\\lceil \\log _2(M)+1 \\rceil +\\varepsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n f<\/mml:mi>\n \n \u2308<\/mml:mo>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n 1<\/mml:mn>\n \u2309<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate integral solution in $$\\begin{aligned} O\\left( (1+f\/\\log n)\\cdot \\left( {\\frac{\\log \\varDelta }{ \\log \\log \\varDelta } + ({f\\cdot \\log M})^{1.01}\\cdot \\log \\varepsilon ^{-1}\\cdot (\\log \\varDelta )^{0.01}}\\right) \\right) \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n O<\/mml:mi>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n f<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n \n \n \n log<\/mml:mo>\n \u0394<\/mml:mi>\n <\/mml:mrow>\n \n log<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n +<\/mml:mo>\n \n \n (<\/mml:mo>\n \n f<\/mml:mi>\n \u00b7<\/mml:mo>\n log<\/mml:mo>\n M<\/mml:mi>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n \n 1.01<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n log<\/mml:mo>\n \n \u03b5<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n 0.01<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:disp-formula>rounds, where f<\/jats:italic> bounds the number of variables in a constraint, $$\\varDelta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bounds the number of constraints a variable appears in, and $$M=\\max \\left\\{ 1, \\lceil 1\/a_{\\min } \\rceil \\right\\} $$<\/jats:tex-math>\n \n M<\/mml:mi>\n =<\/mml:mo>\n max<\/mml:mo>\n \n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2308<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \n a<\/mml:mi>\n min<\/mml:mo>\n <\/mml:msub>\n \u2309<\/mml:mo>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$a_{\\min }$$<\/jats:tex-math>\n \n a<\/mml:mi>\n min<\/mml:mo>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the smallest normalized constraint coefficient.<\/jats:p>","DOI":"10.1007\/s00446-021-00391-w","type":"journal-article","created":{"date-parts":[[2021,4,11]],"date-time":"2021-04-11T07:02:44Z","timestamp":1618124564000},"page":"45-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal distributed covering algorithms"],"prefix":"10.1007","volume":"36","author":[{"given":"Ran","family":"Ben-Basat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Even","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory","family":"Schwartzman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,4,11]]},"reference":[{"key":"391_CR1","doi-asserted-by":"crossref","unstructured":"Astrand, M., Flor\u00e9en, P., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: A local 2-approximation algorithm for the vertex cover problem. In: DISC (2009)","DOI":"10.1007\/978-3-642-04355-0_21"},{"key":"391_CR2","doi-asserted-by":"crossref","unstructured":"Astrand, M., Suomela, J.: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In: SPAA (2010)","DOI":"10.1145\/1810479.1810533"},{"key":"391_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Censor-Hillel, K., Ghaffari, M., Schwartzman, G.: Distributed approximation of maximum independent set and maximum matching. In: ACM, PODC (2017)","DOI":"10.1145\/3087801.3087806"},{"key":"391_CR4","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Censor-Hillel, K., Schwartzman, G.: A distributed $$(2 + \\epsilon )$$- approximation for vertex cover in $$o(log{\\Delta } \/ {\\epsilon } log log {\\Delta })$$ rounds. J. ACM (2017)","DOI":"10.1145\/2933057.2933086"},{"key":"391_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Censor-Hillel, K., Schwartzman, G.: A distributed $$(2 + {\\epsilon })$$- approximation for vertex cover in $$o(log{\\Delta } \/ \\epsilon log log \\Delta )$$ rounds. J. ACM (2017)","DOI":"10.1145\/2933057.2933086"},{"key":"391_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Basat, R., Even, G., Kawarabayashi, K.-I., Schwartzman, G.: A Deterministic distributed $$2$$-approximation for weighted vertex cover in $$O(\\log n\\log \\Delta \/ \\log ^2\\log \\Delta )$$ rounds. In: SIROCCO (2018)","DOI":"10.1007\/978-3-030-01325-7_21"},{"key":"391_CR7","doi-asserted-by":"crossref","unstructured":"Chang, Y., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. In: FOCS (2016)","DOI":"10.1109\/FOCS.2016.72"},{"key":"391_CR8","doi-asserted-by":"crossref","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf Control (1986)","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"391_CR9","unstructured":"Even, G., Ghaffari, M., Medina, M.: Distributed set cover approximation: primal-dual with optimal locality. In: DISC (2018)"},{"key":"391_CR10","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. Soc. Ind. Appl. Math. SODA (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"391_CR11","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Su, H.: Distributed degree splitting, edge coloring, and orientations. In: SODA (2017)","DOI":"10.1137\/1.9781611974782.166"},{"key":"391_CR12","doi-asserted-by":"crossref","unstructured":"Grandoni, F., K\u00f6nemann, J., Panconesi, A.: Distributed weighted vertex cover via maximal matchings. ACM Trans. Algorithms (2008)","DOI":"10.1145\/1435375.1435381"},{"key":"391_CR13","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. (1982)","DOI":"10.1137\/0211045"},{"key":"391_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"391_CR15","doi-asserted-by":"crossref","unstructured":"Khuller, S., Vishkin, U., Young, N.E.: A primal-dual parallel approximation technique applied to weighted set and vertex covers. J. Algorithms (1994)","DOI":"10.1006\/jagm.1994.1036"},{"key":"391_CR16","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Distributed algorithms for covering, packing and maximum weighted matching. Distrib. Comput. (2011)","DOI":"10.1007\/s00446-011-0127-7"},{"key":"391_CR17","unstructured":"Kuhn, F.: The price of locality: exploring the complexity of distributed coordination primitives. PhD thesis, ETH Zurich (2005)"},{"key":"391_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: SODA (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"391_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: Lower and upper bounds. J. ACM (2016)","DOI":"10.1145\/2742012"},{"key":"391_CR20","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. (2001)","DOI":"10.1007\/PL00008932"},{"key":"391_CR21","doi-asserted-by":"crossref","unstructured":"Polishchuk, V., Suomela, J.: A simple local 3-approximation algorithm for vertex cover. Inf. Process. Lett. (2009)","DOI":"10.1016\/j.ipl.2009.02.017"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00391-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00391-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00391-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,4]],"date-time":"2023-03-04T09:04:09Z","timestamp":1677920649000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00391-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,11]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["391"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00391-w","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,11]]},"assertion":[{"value":"11 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}