Approximation algorithms for combinatorial optimization problems
Approximation algorithms for combinatorial optimization problems
复制标题
组合优化问题的近似算法
DOI：
--
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
Frank D. Murgolo
中科院分区：
文献类型：
--
作者：
Frank D. Murgolo
组合近似问题在理论和实践中经常出现。这些问题中的许多都可以在合理的时间内完全解决。因此，人们试图开发有效的近似算法，这些算法可以在可行的时间内解决这些问题，并产生在可接受的误差耐受性范围内的解决方案。在本文中研究的问题是bin包装问题，就是一个问题。在此问题中，给出了一组项目，并要求将它们包装到最小垃圾箱中，以使每个垃圾桶中的物品大小的总和不超过垃圾箱容量。这个问题的某些算法具有有时使用更多垃圾箱包装的少量项目的不良质量，而这些算法比打包了一个大列表，该列表是通过增加小列表中某些项目的大小而得出的更大列表。我们研究了有关这种异常行为的大量垃圾箱包装算法。对于此类中的许多算法，我们确定哪些是异常的，哪些不是。我们发现这些算法上的上限和下限是异常的，并研究了该类别中算法的有趣特性。
本文还研究了可变尺寸的垃圾箱包装问题。在标准箱填料问题的这种概括中，用于包装的垃圾箱具有不同的尺寸，并且希望最大程度地减少包装中使用的垃圾箱的大小。这个问题也称为切割库存问题，非常重要，并且经常出现。我们开发了一个近似方案，该方案作为输入此问题的实例和一个错误绑定（Epsilon），并作为输出算法产生，并且在包装的项目和1/（Epsilon）中，运行时间多项式具有多项式。
Combinatorial approximation problems arise frequently in both theory and practice. Many of these problems resist being solved exactly in a reasonable amount of time. For this reason, people try to develop efficient approximation algorithms which can solve these problems in a feasible amount of time, and which produce solutions that are within an acceptable error tolerance. The problem examined in this thesis, the bin packing problem, is one such problem. In this problem one is given a set of items and asked to pack them into the minimum number of bins so that the sum of the item sizes in each bin is no greater than the bin capacity. Some algorithms for this problem possess the undesirable quality of sometimes using more bins to pack a small list of items than they do to pack a larger list which is derived by increasing the size of some of the items in the small list. We study a large class of bin packing algorithms with regard to this type of anomalous behavior. For many algorithms in this class we determine which are anomalous and which are not. We find upper and lower bounds on those algorithms which are anomalous and investigate interesting properties of algorithms in this class.
This thesis also examines the variable-sized bin packing problem. In this generalization of the standard bin packing problem, the bins used for packing are of various different sizes and one wishes to minimize the sum of the sizes of bins used in the packing. This problem, which is also called the cutting stock problem, is of practical importance and arises frequently. We develop an approximation scheme which takes as input an instance of this problem and an error bound (epsilon) and produces as output an algorithm with a running time polynomial in both the number of items being packed and 1/(epsilon).