Approximate Graph Coloring by Semideenite Programming
Approximate Graph Coloring by Semideenite Programming
复制标题
通过 Semideenite 编程进行近似图形着色
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
R. Motwani
中科院分区：
文献类型：
--
作者：
R. Motwani
我们考虑用最少可能的颜色为k-可色图着色的问题。我们提出了一种随机多项式时间算法，该算法使用minfO（(1=3 log 4=3)）对n个顶点上的3色图进行上色；O(n 1=4 logn)g个颜色，其中是任意顶点的最大度数。除了给出以n表示的最著名的近似比之外，这标志着第一个非平凡近似结果是最大度的函数。此结果可推广到k-可着色图，利用minf ~ O(（1?2=k）得到一个着色；~ O(n 1？3 g = (k + 1))的颜色。我们的结果受到Goemans和Williamson （GW93）最近工作的启发，他们使用了一种算法来解决半离散优化问题（参见GLS81， Ali92），该算法推广了线性规划，以获得MAX CUT和MAX 2-SAT问题的改进近似。我们工作的一个有趣的结果是在我们的半识别程序的最优解的值和lovvasz#函数之间建立了对偶关系。给出了半恒等式最优解与实际色数之间的下界；通过对偶性，这也证明了关于#-函数有趣的新事实。
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with minfO((1=3 log 4=3); O(n 1=4 logn)g colors where is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the rst non-trivial approximation result as a function of the maximum degree. This result can be generalized to k-colorable graphs to obtain a coloring using minf ~ O((1?2=k); ~ O(n 1?3=(k+1))g colors. Our results are inspired by the recent work of Goemans and Williamson GW93] who used an algorithm for semideenite optimization problems (cf. GLS81, Ali92]), which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semideenite program and the Lovv asz #-function. We show lower bounds on the gap between the optimum solution of our semideenite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the #-function.