Name
Abstract | ||
|---|---|---|
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover hypergraphs of rank $f$. This problem is equivalent to the Minimum Weight Set Cover Problem which the frequency of every element is bounded by $f$. The approximation factor of our algorithm is $(f+epsilon)$. Let $Delta$ denote the maximum degree the hypergraph. Our algorithm runs the CONGEST model and requires $O(log{Delta} / log log Delta)$ rounds, for constants $epsilon in (0,1]$ and $finmathbb N^+$. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights or the number of vertices. Thus adding another member to the exclusive family of emph{provably optimal} distributed algorithms. For constant values of $f$ and $epsilon$, our algorithm improves over the $(f+epsilon)$-approximation algorithm of cite{KuhnMW06} whose running time is $O(log Delta + log W)$, where $W$ is the ratio between the largest and smallest vertex weights the graph. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Distributed, Parallel, and Cluster Computing | Combinatorics,Vertex (geometry),Computer science,Constraint graph,Hypergraph,Real-time computing,Distributed algorithm,Degree (graph theory),Minimum weight,Vertex cover,Bounded function |
DocType | Volume | Citations |
Journal | abs/1808.05809 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ran Ben-Basat | 1 | 105 | 19.20 |
| Guy Even | 2 | 1194 | 136.90 |
| Ken-ichi Kawarabayashi | 3 | 1731 | 149.16 |
| Gregory Schwartzman | 4 | 0 | 1.35 |