Matched approximation bound for the sum of a greedy coloring

Amotz Bar-Noy; Magnús M. Halldórsson; Guy Kortsarz

doi:10.1016/S0020-0190(99)00104-0

Matched approximation bound for the sum of a greedy coloring

Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

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 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).

Original language	American English
Pages (from-to)	135-140
Number of pages	6
Journal	Information Processing Letters
Volume	71
Issue number	3
DOIs	https://doi.org/10.1016/S0020-0190(99)00104-0
State	Published - Aug 27 1999
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/S0020-0190(99)00104-0

Cite this

@article{a34b554ca59344d7aa6d7516371f4cc0,

title = "Matched approximation bound for the sum of a greedy coloring",

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 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).",

author = "Amotz Bar-Noy and Halld{\'o}rsson, {Magn{\'u}s M.} and Guy Kortsarz",

year = "1999",

month = aug,

day = "27",

doi = "10.1016/S0020-0190(99)00104-0",

language = "American English",

volume = "71",

pages = "135--140",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "3",

}

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

UR - http://www.scopus.com/inward/citedby.url?scp=0033609577&partnerID=8YFLogxK

U2 - 10.1016/S0020-0190(99)00104-0

DO - 10.1016/S0020-0190(99)00104-0

M3 - Article

SN - 0020-0190

VL - 71

SP - 135

EP - 140

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Matched approximation bound for the sum of a greedy coloring

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this