论文标题
改进了图形加权边缘着色的近似算法
Improved Approximation Algorithms for Weighted Edge Coloring of Graphs
论文作者
论文摘要
我们研究图形的加权边缘着色，在其中为我们提供了无向的边缘加权多盖$ g：=（v，e）$，重量$ w：e \ rightarrow [0，1] $。目的是找到具有尽可能少的颜色的边缘的适当加权着色。如果边缘的重量总和到任何颜色的顶点，则边缘着色称为适当的加权着色。在在线环境中，边缘逐一揭示，必须在揭露后立即不可撤销。我们表明，当所有顶点的顶点的最大邻居数为$ o（m）$时，$ 339万美元+（m）$颜色就足够了，而$ m $是将事件边缘重量装载到该顶点所需的最小单位箱数量的所有最小值的最大值。我们还证明了分析的紧密性。这在Correa and Goemans的500万美元最佳上限上得到了改善[Stoc 2004]。对于离线情况，我们表明，对于带有边缘脱节周期的简单图，$ m+1 $颜色就足够了，对于多画树，我们表明$ 169.3万美元+12美元的颜色就足够了。
We study weighted edge coloring of graphs, where we are given an undirected edge-weighted general multi-graph $G := (V, E)$ with weights $w : E \rightarrow [0, 1]$. The goal is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. In the online setting, the edges are revealed one by one and have to be colored irrevocably as soon as they are revealed. We show that $3.39m+o(m)$ colors are enough when the maximum number of neighbors of a vertex over all the vertices is $o(m)$ and where $m$ is the maximum over all vertices of the minimum number of unit-sized bins needed to pack the weights of the incident edges to that vertex. We also prove the tightness of our analysis. This improves upon the previous best upper bound of $5m$ by Correa and Goemans [STOC 2004]. For the offline case, we show that for a simple graph with edge disjoint cycles, $m+1$ colors are sufficient and for a multi-graph tree, we show that $1.693m+12$ colors are sufficient.
