Brief Announcement: Optimal Distributed Covering Algorithms

Ran Ben Basat, Guy Even, Ken Ichi Kawarabayashi, Gregory Schwartzman

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f . This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f . The approximation factor of our algorithm is (f +ϵ). Let δ denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requiresO(log δ/log log δ) rounds, for constants ϵ ϵ (0, 1] and f ϵ ℕ+. 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 distributed algorithms. For constant values of f and ϵ, our algorithm improves over the (f + ϵ)-approximation algorithm of [16] whose running time is O(log δ + logW), whereW is the ratio between the largest and smallest vertexweights in the graph. Our algorithm also achieves an f -approximation for the problem in O(f logn) rounds, improving over the classical result of [13] that achieves a running time of O(f log2 n). Finally, forweighted vertex cover (f = 2) our algorithm achieves a deterministic running time of O(logn), matching the randomized previously best result of [14]. 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 +ϵ)-approximate integral solution in (equation presented) rounds, where f bounds the number of variables in a constraint, δ bounds the number of constraints a variable appears in, and M = max {1, 1/amin}, where amin is the smallest normalized constraint coefficient. This significantly improves over the results of [16] for the integral case, which achieves the same guarantees in O (ϵ-4 · f4 · log f · log(M · δ) rounds.

שפה מקוריתאנגלית
כותר פרסום המארחPODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
מספר עמודים3
מסת"ב (אלקטרוני)9781450362177
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 16 יולי 2019
אירוע38th ACM Symposium on Principles of Distributed Computing, PODC 2019 - Toronto, קנדה
משך הזמן: 29 יולי 20192 אוג׳ 2019

סדרות פרסומים

שםProceedings of the Annual ACM Symposium on Principles of Distributed Computing


כנס38th ACM Symposium on Principles of Distributed Computing, PODC 2019

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.1700.1708???
  • ???subjectarea.asjc.1700.1705???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Brief Announcement: Optimal Distributed Covering Algorithms'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי