Matched approximation bound for the sum of a greedy coloring

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

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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

שפה מקוריתאנגלית
עמודים (מ-עד)135-140
מספר עמודים6
כתב עתInformation Processing Letters
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 27 אוג׳ 1999

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Matched approximation bound for the sum of a greedy coloring'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי