A matched approximation bound for the sum of a greedy coloring

Authors
Bar-Noy, A Halldorsson, MM Kortsarz, G
Citation
A. Bar-noy et al., A matched approximation bound for the sum of a greedy coloring, INF PROCESS, 71(3-4), 1999, pp. 135-140
Citations number
9
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
71
Issue
3-4
Year of publication
1999
Pages
135 - 140
Database
ISI
SICI code
0020-0190(19990827)71:3-4<135:AMABFT>2.0.ZU;2-W
Abstract
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 minima l. 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 app roximation ratio of this coloring is 4 - o(1). (C) 1999 Published by Elsevi er Science B.V. All rights reserved.