论文标题
分数着色的分布式算法
Distributed algorithms for fractional coloring
论文作者
论文摘要
在本文中，我们从分布式计算角度研究分数着色。分数着色是古典着色概念的线性松弛，并且具有许多应用，特别是在调度方面。 Hasemann，Hirvonen，Rybicki和Suomela（2016）证明了每一个实际$α> 1 $和整数$δ$，最多可以在本地模型的最高学位$δ$ $δ$的图中确定总重量（δ+1）$的总重量（δ+1）$。但是，这个结果的一个主要问题是每个顶点的输出的大小无限。在这里，我们证明，即使我们施加了更现实的假设，即每个顶点的输出具有恒定的大小，我们也可以在几种感兴趣的情况下，发现对分数色数任意接近已知的紧密界限的总重量。更确切地说，我们表明，对于任何固定的$ε> 0 $和$δ$，总重量最多可以在$ o（\ log^*n）$ rounds中找到最大$δ$的$Δ$ no $ k_ {δ+1} $的$Δ$的圆形$δ$Δ$ aigry的$δ$Δ$Δ$Δ随机算法和$ω（\ log n）$ rounds的回合，用于确定性算法。我们还展示了如何获得任何固定尺寸的网格的总重量的分数色素，对于任何$ε> 0 $，以$ O（\ log^*n）$ rounds为$ε> 0 $。最后，我们证明，在任何适当的次要封闭家庭的稀疏图中，我们都可以找到总重量的分数着色，最多$ 2+ε$，对于任何$ε> 0 $，以$ o（\ log n）$ rounds中的任何$ε> 0 $。
In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It was proved by Hasemann, Hirvonen, Rybicki and Suomela (2016) that for every real $α>1$ and integer $Δ$, a fractional coloring of total weight at most $α(Δ+1)$ can be obtained deterministically in a single round in graphs of maximum degree $Δ$, in the LOCAL model of computation. However, a major issue of this result is that the output of each vertex has unbounded size. Here we prove that even if we impose the more realistic assumption that the output of each vertex has constant size, we can find fractional colorings of total weight arbitrarily close to known tight bounds for the fractional chromatic number in several cases of interest. More precisely, we show that for any fixed $ε> 0$ and $Δ$, a fractional coloring of total weight at most $Δ+ε$ can be found in $O(\log^*n)$ rounds in graphs of maximum degree $Δ$ with no $K_{Δ+1}$, while finding a fractional coloring of total weight at most $Δ$ in this case requires $Ω(\log \log n)$ rounds for randomized algorithms and $Ω( \log n)$ rounds for deterministic algorithms. We also show how to obtain fractional colorings of total weight at most $2+ε$ in grids of any fixed dimension, for any $ε>0$, in $O(\log^*n)$ rounds. Finally, we prove that in sparse graphs of large girth from any proper minor-closed family we can find a fractional coloring of total weight at most $2+ε$, for any $ε>0$, in $O(\log n)$ rounds.
