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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2007
الحدث15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, إسرائيل
المدة: ٨ أكتوبر ٢٠٠٧١٠ أكتوبر ٢٠٠٧

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4698 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference15th Annual European Symposium on Algorithms, ESA 2007


أدرس بدقة موضوعات البحث “Approximating interval scheduling problems with bounded profits'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا