...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Vector bin packing with multiple-choice
【24h】

Vector bin packing with multiple-choice

机译：矢量箱包装有多项选择

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider a variant of bin packing called multiple-choice vector bin packing. In this problem, we are given a set of n items, where each item can be selected in one of several D-dimensional incarnations. We are also given T bin types, each with its own cost andD-dimensional size. Our goal is to pack the items in a set of bins of minimum overall cost. The problem is motivated by scheduling in networks with guaranteed quality of service (QoS), but due to its general formulation it has many other applications as well. We present an approximation algorithm that is guaranteed to produce a solution whose cost is about lnD times the optimum. For the running time to be polynomial we require D=O(1) and T=O(logn). This extends previous results for vector bin packing, in which each item has a single incarnation and there is only one bin type. To obtain our result we also present a PTAS for the multiple-choice version of multidimensional knapsack, where we are given only one bin and the goal is to pack a maximum weight set of (incarnations of) items in that bin.
机译：我们考虑bin打包的一种变体，称为多选向量bin打包。在这个问题中，我们得到了一组n个项目，其中每个项目都可以从多个D维化身中选择。我们还获得了T箱类型，每种都有自己的成本和D维尺寸。我们的目标是将物品包装在最低总成本的一组垃圾箱中。该问题是由在具有保证的服务质量（QoS）的网络中进行调度引起的，但是由于其一般性的表述，它也有许多其他应用。我们提出了一种近似算法，可以保证产生一种解决方案，其成本约为lnD乘以最优值。为了使运行时间为多项式，我们需要D = O（1）和T = O（logn）。这扩展了以前的矢量装箱结果，其中每个物品都有一个化身，并且只有一个装箱类型。为了获得我们的结果，我们还为多维背包的多选择版本提供了PTAS，其中仅给我们一个垃圾箱，目标是在该垃圾箱中装满最大重量的一组物品。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号