首页> 外文会议>Annual IEEE Symposium on Foundations of Computer Science >Improved approximation algorithms for multidimensional bin packing problems
【24h】

Improved approximation algorithms for multidimensional bin packing problems

机译:改进多维箱包装问题的近似算法

获取原文

摘要

In this paper we introduce a new general framework for set covering problems, based on the combination of randomized rounding of the (near-)optimal solution of the Linear Programming (LP) relaxation, leading to a partial integer solution, and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. Applying our general framework we obtain a polynomial-time randomized algorithm for d-dimensional vector packing with approximation guarantee arbitrarily close to ln d+1. For d=2, this value is.1.693..., i.e., we break the natural 2 "barrier" for this case. Moreover, for small values of d this is a notable improvement over the previously-known O(ln d) guarantee by Chekuri and Khanna [5]. For 2-dimensional bin packing with and without rotations, we construct algorithms with performance guarantee arbitrarily close to 1.525..., improving upon previous algorithms with performance guarantee of 2+ε by Jansen and Zhang [12] for the problem with rotations and 1.691... by Caprara [2] for the problem without rotations. The previously-unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker [7]. We prove that their approximation scheme is "subset oblivious", which leads to numerous applications. Another byproduct of our paper is an algorithm that solves a well-known configuration LP for 2-dimensional bin packing within a factor of(1+ε) for any ε>0. Interestingly, we do it without using an approximate separation oracle, which would correspond to a well-known geometric 2-dimensional knapsack. Although separation and optimization are equivalent [10] and the existence of an approximation scheme for the separation problem remains open, we are able to design an approximation scheme for the configuration LP since its objective function is unweighed.
机译:在本文中,我们引入一个新的总体框架集合覆盖的问题的基础上,结合随机化舍入线性规划(LP)松弛的(近)的最优解,导致局部整数解,和一个应用乖巧的近似算法来完成这个解决方案。如果由后者返回的溶液的值可以以适当的方式来界定,如对于装箱的最相关的概括,该方法导致改进的近似的保证的情况下,更严格的完整性间隙对于LP证明沿松弛。运用我们的总体框架,我们得到一个多项式时间随机与近似保证d维向量打包算法任意接近LN d + 1。对于d = 2,此值is.1.693 ...,即,我们打破这种情况下,天然2“屏障”。此外,对于d的小的值,这是在先前已知的O(LN d)通过Chekuri和卡纳[5]保证的显着改善。对于有和没有旋转的2维装箱,我们构造与性能保证算法任意接近1.525 ...,用2履约担保+ε由扬森和张[12]用旋转和1.691的问题在以前的算法改进...通过卡普拉拉[2]不旋转的问题。在我们的证明中使用的以前未知的关键属性由费尔南德斯·德拉维加和Lueker [7]地标装箱近似算法的影响的回顾性分析如下。我们证明了他们的近似方案“子集遗忘”,这导致了大量的应用。我们的纸张的另一副产物是一种算法,解决了公知的结构为LP 2维装箱的(1 +ε)为任何ε> 0倍之内。有趣的是,我们做没有使用近似分离预言,这将对应于公知的几何2维背包。虽然分离和优化是等价的[10]和用于分离问题的近似方案的存在仍然开放,我们能够因为其目标函数是unweighed设计一个近似方案为配置LP。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号