An AFPTAS for variable sized bin packing with general activation costs
详细信息 查看全文
- 作者：Leah Epsteina ; lea@math.haifa.ac.il" class="auth_mail" title="E-mail the corresponding author ; Asaf Levinb ; levinas@ie.technion.ac.il" class="auth_mail" title="E-mail the corresponding author
- 关键词：Bin packing ; Asymptotic approximation schemes ; Scheduling
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：79-96
- 全文大小：626 K
文摘
- class="listitem" id="list_ls0010">
- class="label">•
AFPTAS for general cost variable size bin packing.
- class="label">•
AFPTAS for due date scheduling with general activation cost on related machines.
- class="label">•
Series of reductions leading to a non-standard application of the shifting technique.
- class="label">•
Shifting gives almost independent subproblems whose solutions are combined via DP.
- class="label">•
Oracle based formulation of an AFPTAS for bin packing with general utilization cost.