Approximability issues for unconstrained and constrained maximization of half-product related functions

详细信息    查看全文

• 作者：Hans Kellererp>ap>p> ; p>p>hans.kellerer@uni-graz.atp> ; Rebecca Sarto Bassop>bp>p> ; p>p>rebeccasarto@berkeley.edup> ; Vitaly A. Strusevichp>cp>p> ; p>p>V.Strusevich@greenwich.ac.ukp>
• 关键词：Half-product ; Quadratic knapsack ; Non-approximability ; FPTAS
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：659
• 期：Complete
• 页码：64-71
• 全文大小：293 K
• 卷排序：659

文摘

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.