FPTAS for half-products minimization with scheduling applications |
| |
Authors: | Erdal Erel Jay B. Ghosh |
| |
Affiliation: | a Faculty of Business Administration, Bilkent University, 06800 Bilkent, Ankara, Turkey b Korea University Business School, Korea University, Seoul, Korea |
| |
Abstract: | 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. |
| |
Keywords: | Quadratic pseudo-boolean functions Dynamic programming Approximation scheme |
本文献已被 ScienceDirect 等数据库收录! |
|