کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420518 | 683951 | 2008 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
FPTAS for half-products minimization with scheduling applications
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A special class of quadratic pseudo-boolean functions called “half-products” (HP) has recently been introduced. It has been shown that HP minimization, while NP-hard, admits a fully polynomial time approximation scheme (FPTAS). In this note, we provide a more efficient FPTAS. We further show how an FPTAS can also be derived for the general case where the HP function is augmented by a problem-dependent constant and can justifiably be assumed to be nonnegative. This leads to an FPTAS for certain partitioning type problems, including many from the field of scheduling.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 15, 6 August 2008, Pages 3046–3056
Journal: Discrete Applied Mathematics - Volume 156, Issue 15, 6 August 2008, Pages 3046–3056
نویسندگان
Erdal Erel, Jay B. Ghosh,