着色 - 空宝网

标签:着色

计算机科学

2D矩形着色问题是否存在常数因子近似算法?

2D矩形着色问题是否存在常数因子近似算法?
我们在这里考虑的问题是众所周知的区间着色问题的扩展。我们考虑的是具有与轴平行的边的矩形,而不是间隔。目标是使用最少数量的颜色为矩形着色,使得任何两个重叠的矩形被分配不同的颜色。 已知这个问题是NP难的。(近似框图上的最大独立集和最小顶点着色)给出了O(log n)近似值。有更好的近似算法吗? 我们知道,通过根据左端点考虑间隔,通过首次拟合算法在多项式时间内求……继续阅读 »

0个赞