TY - JOUR
T1 - Matched approximation bound for the sum of a greedy coloring
AU - Bar-Noy, Amotz
AU - Halldórsson, Magnús M.
AU - Kortsarz, Guy
PY - 1999/8/27
Y1 - 1999/8/27
N2 - In the minimum sum coloring problem, the goal is to color the vertices of a graph with the positive integers such that the sum of all colors is minimal. Iteratively coloring maximum independent sets has been shown to yield a 4+o(1) approximation for the minimum sum coloring problem. In this note, we show that this bound is tight, by constructing a graph for which the approximation ratio of this coloring is 4-o(1).
AB - In the minimum sum coloring problem, the goal is to color the vertices of a graph with the positive integers such that the sum of all colors is minimal. Iteratively coloring maximum independent sets has been shown to yield a 4+o(1) approximation for the minimum sum coloring problem. In this note, we show that this bound is tight, by constructing a graph for which the approximation ratio of this coloring is 4-o(1).
UR - http://www.scopus.com/inward/record.url?scp=0033609577&partnerID=8YFLogxK
U2 - 10.1016/S0020-0190(99)00104-0
DO - 10.1016/S0020-0190(99)00104-0
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:0033609577
SN - 0020-0190
VL - 71
SP - 135
EP - 140
JO - Information Processing Letters
JF - Information Processing Letters
IS - 3
ER -