Computer Science – Data Structures and Algorithms
Scientific paper
1998-12-08
JACM 45(2), mar. 1998, pp.246--265
Computer Science
Data Structures and Algorithms
Scientific paper
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on $n$ vertices with min O(Delta^{1/3} log^{1/2} Delta log n), O(n^{1/4} log^{1/2} n) colors where Delta is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree Delta. This result can be generalized to k-colorable graphs to obtain a coloring using min O(Delta^{1-2/k} log^{1/2} Delta log n), O(n^{1-3/(k+1)} log^{1/2} n) colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, 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 semidefinite program and the Lovasz theta-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the theta-function.
Karger David
Motwani Rajeev
Sudan Madhu
No associations
LandOfFree
Approximate Graph Coloring by Semidefinite Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximate Graph Coloring by Semidefinite Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Graph Coloring by Semidefinite Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-310293