Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952310 | Theoretical Computer Science | 2017 | 12 Pages |
Abstract
We address the Boolean programming problem of maximizing a half-product function, with and without a linear knapsack constraint. Maximizing the half-product can be done in polynomial time. Adding a knapsack constraint makes the problem non-approximable within a constant factor, provided that the coefficients in the linear part of the function are negative. For maximizing a function with positive coefficients in the linear part we develop a fully polynomial-time approximation scheme.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hans Kellerer, Rebecca Sarto Basso, Vitaly A. Strusevich,