TY - GEN
T1 - Approximating interval scheduling problems with bounded profits
AU - Beniaminy, Israel
AU - Nutov, Zeev
AU - Ovadia, Meir
PY - 2007
Y1 - 2007
N2 - We consider the Generalized Scheduling Within Intervals (GSWI) problem: given a set J of jobs and a set J of intervals, where each job j ∈ J has in interval I ∈ I length (processing time) ℓj,I and profit Pj, I, find the highest-profit feasible schedule. The best approximation ratio known for GSWI is (1/2 - ε). We give a (1 - 1/e - ε)-approximation scheme for GSWI with bounded profits, based on the work by Chuzhoy, Rabani, and Ostrovsky [4] for the {0, l}-profit case. We also consider the Scheduling Within Intervals (SWI) problem, which is a particular case of GSWI where for every j ∈ J there is a unique interval I = Ij ∈ I with Pj,I > 0. We prove that SWI is (weakly) NP-hard even if the stretch factor (the maximum ratio of job's interval size to its processing time) is arbitrarily small, and give a polynomial-time algorithm for bounded profits and stretch factor < 2.
AB - We consider the Generalized Scheduling Within Intervals (GSWI) problem: given a set J of jobs and a set J of intervals, where each job j ∈ J has in interval I ∈ I length (processing time) ℓj,I and profit Pj, I, find the highest-profit feasible schedule. The best approximation ratio known for GSWI is (1/2 - ε). We give a (1 - 1/e - ε)-approximation scheme for GSWI with bounded profits, based on the work by Chuzhoy, Rabani, and Ostrovsky [4] for the {0, l}-profit case. We also consider the Scheduling Within Intervals (SWI) problem, which is a particular case of GSWI where for every j ∈ J there is a unique interval I = Ij ∈ I with Pj,I > 0. We prove that SWI is (weakly) NP-hard even if the stretch factor (the maximum ratio of job's interval size to its processing time) is arbitrarily small, and give a polynomial-time algorithm for bounded profits and stretch factor < 2.
UR - http://www.scopus.com/inward/record.url?scp=38049085738&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-75520-3_44
DO - 10.1007/978-3-540-75520-3_44
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:38049085738
SN - 9783540755197
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 487
EP - 497
BT - Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
PB - Springer Verlag
T2 - 15th Annual European Symposium on Algorithms, ESA 2007
Y2 - 8 October 2007 through 10 October 2007
ER -