论文标题
增量背包问题的近似动态编程方法
An Approximate Dynamic Programming Approach to The Incremental Knapsack Problem
论文作者
论文摘要
我们研究了增量背包问题，其中希望将物品依次包装到一个背包中，其容量在有限的计划范围内扩展，目的是最大限度地利用了时间平均的利润。虽然在缓解结构假设下开发了各种近似算法，但以最大的一般性获得了该问题的非平凡绩效保证，迄今为止仍然是一个悬而未决的问题。在本文中，我们设计了一个多项式时间近似方案，用于增量背包问题的一般实例，这是鉴于现有的硬度结果，这是最强大的保证。与较早的工作相反，我们的算法方法利用了近似的动态编程公式。从一个简单的指数尺寸的动态程序开始，我们证明，适当的状态修剪想法的成分产生了一个多条尺寸的状态空间，而最佳损失却可以忽略不计。对该公式的分析综合了各种技术，包括新的问题分解，简约的计数论点和有效的舍入方法，可能会引起广泛关注。
We study the incremental knapsack problem, where one wishes to sequentially pack items into a knapsack whose capacity expands over a finite planning horizon, with the objective of maximizing time-averaged profits. While various approximation algorithms were developed under mitigating structural assumptions, obtaining non-trivial performance guarantees for this problem in its utmost generality has remained an open question thus far. In this paper, we devise a polynomial-time approximation scheme for general instances of the incremental knapsack problem, which is the strongest guarantee possible given existing hardness results. In contrast to earlier work, our algorithmic approach exploits an approximate dynamic programming formulation. Starting with a simple exponentially sized dynamic program, we prove that an appropriate composition of state pruning ideas yields a polynomially sized state space with negligible loss of optimality. The analysis of this formulation synthesizes various techniques, including new problem decompositions, parsimonious counting arguments, and efficient rounding methods, that may be of broader interest.
