BOUNDING THE RUNNING TIME OF ALGORITHMS FOR SCHEDULING AND PACKING PROBLEMS
BOUNDING THE RUNNING TIME OF ALGORITHMS FOR SCHEDULING AND PACKING PROBLEMS
复制标题
DOI：
10.1137/140952636
复制
发表时间：
2016-01-01
影响因子：
0.8
通讯作者：
Land, K.
中科院分区：
文献类型：
--
作者：
Jansen, K.;Land, F.;Land, K.
我们的目标是显示调度和布局问题算法的运行时间的严格界限。为了证明下界，我们研究了指数时间假设对这类算法的影响。对于精确的算法，我们考虑了运行时间对物品(用于包装)或作业(用于调度)数量n的依赖关系。我们证明了2(o(N))x垂直条垂直条i垂直条垂直条(O(N))的下界，其中垂直条垂直条i垂直条表示实例的编码长度，对于其中的几个问题，包括SUBSETSUM、背包、BINPACKING、<；P2垂直条垂直条C-max>；和<；P2垂直条垂直条Sigma w(J)C(J)>；。我们还开发了一个算法框架，能够在时间为20(N)x垂直条i垂直条(O(N))内解决大量的调度和布局问题。最后，我们考虑了近似格式。我们证明了运行时间分别为2(o(1/epsilon))×竖杆i竖杆(O(N))和n(o(1/epsilon))x竖杆i竖杆(O(N))的MKS和2D背包不存在多项式时间逼近方案。
Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We prove a lower bound of 2(o(n)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), where vertical bar vertical bar I vertical bar vertical bar denotes the encoding length of the instance, for several of these problems, including SUBSETSUM, KNAPSACK, BINPACKING, < P2 vertical bar vertical bar C-max >, and < P2 vertical bar vertical bar Sigma w(j)C(j)>. We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2o(n) x vertical bar vertical bar I vertical bar vertical bar(O(n)). Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MULTIPLEKNAPSACK (MKS) and 2D-KNAPSACK with running time 2(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)) and n(o(1/epsilon)) x vertical bar vertical bar I vertical bar vertical bar(O(n)), respectively.