TY - GEN

T1 - Inverse booking problem

T2 - 2nd International Workshop on Algorithms and Computation, WALCOM 2008

AU - Chung, Yerim

AU - Culus, Jean François

AU - Demange, Marc

PY - 2008

Y1 - 2008

N2 - We consider inverse chromatic number problems in interval graphs having the following form: we are given an integer K and an interval graph G = (V,E), associated with n = |V| intervals I i = ]a i ,b i [ (1 ≤ i ≤ n), each having a specified length s(I i ) = b i - a i , a (preferred) starting time a i and a completion time b i . The intervals are to be newly positioned with the least possible discrepancies from the original positions in such a way that the related interval graph can be colorable with at most K colors. We propose a model involving this problem called inverse booking problem.We show that inverse booking problems are hard to approximate within O(n 1 - ε ), ε > 0 in the general case with no constraints on lengths of intervals, even though a ratio of n can be achieved by using a result of [13]. This result answers a question recently formulated in [12] about the approximation behavior of the unweighted case of single machine just-in-time scheduling problem with earliness and tardiness costs. Moreover, this result holds for some restrictive cases.

AB - We consider inverse chromatic number problems in interval graphs having the following form: we are given an integer K and an interval graph G = (V,E), associated with n = |V| intervals I i = ]a i ,b i [ (1 ≤ i ≤ n), each having a specified length s(I i ) = b i - a i , a (preferred) starting time a i and a completion time b i . The intervals are to be newly positioned with the least possible discrepancies from the original positions in such a way that the related interval graph can be colorable with at most K colors. We propose a model involving this problem called inverse booking problem.We show that inverse booking problems are hard to approximate within O(n 1 - ε ), ε > 0 in the general case with no constraints on lengths of intervals, even though a ratio of n can be achieved by using a result of [13]. This result answers a question recently formulated in [12] about the approximation behavior of the unweighted case of single machine just-in-time scheduling problem with earliness and tardiness costs. Moreover, this result holds for some restrictive cases.

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

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

U2 - 10.1007/978-3-540-77891-2_17

DO - 10.1007/978-3-540-77891-2_17

M3 - Conference contribution

AN - SCOPUS:49949085388

SN - 354077890X

SN - 9783540778905

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 180

EP - 187

BT - WALCOM

Y2 - 7 February 2008 through 8 February 2008

ER -