Approximating interval scheduling problems with bounded profits

Israel Beniaminy, Zeev Nutov, Meir Ovadia

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


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.

שפה מקוריתאנגלית
כותר פרסום המארחAlgorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
מוציא לאורSpringer Verlag
מספר עמודים11
מסת"ב (מודפס)9783540755197
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2007
אירוע15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, ישראל
משך הזמן: 8 אוק׳ 200710 אוק׳ 2007

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך4698 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס15th Annual European Symposium on Algorithms, ESA 2007

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating interval scheduling problems with bounded profits'. יחד הם יוצרים טביעת אצבע ייחודית.

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