Differential approximation schemes for half-product related functions and their scheduling applications

详细信息    查看全文

• 作者：Rebecca Sarto Basso^a ; ^{rebeccasarto@berkeley.edu} ; Vitaly A. Strusevich^b ; ^{V.Strusevich@gre.ac.uk}
• 关键词：Half-product ; Quadratic knapsack ; FPTAS ; Differential approximation schemes
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P1
• 页码：71-78
• 全文大小：417 K
• 卷排序：217

文摘

We address the problem of minimizing a half-product function, with and without a linear knapsack constraint. We show how to convert known fully polynomial-time approximation schemes to differential approximation schemes that handle the problems with and without an additive constant and with and without a linear knapsack constraint. Thereby, we resolve the issue of differential approximation for a range of scheduling problems.