...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >A note on online strip packing
【24h】

A note on online strip packing

机译：在线包装带的注意事项

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

摘要

In online strip packing we are asked to pack a list of rectangles one by one into a vertical strip of unit width, without any information about future rectangles. The goal is to minimize the total height of strip used. The best known algorithm is First Fit Shelf algorithm (Baker and Schwarz in SIAM J. Comput. 12(3):508–525, 1983), which has an absolute competitive ratio of 6.99 under the assumption that the height of each rectangle is bounded from above by one. We improve the shelf algorithm and show an absolute competitive ratio of $7/2+sqrt{10}approx 6.6623$ without the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling.
机译：在在线带包装中，我们被要求将矩形列表一一打包到单位宽度的垂直带中，而无需任何有关未来矩形的信息。目的是使所使用的带材的总高度最小化。最著名的算法是First Fit Shelf算法（Baker和Schwarz in SIAM J. Comput。12（3）：508-525，1983年），在假设每个矩形的高度有界的情况下，其绝对竞争比为6.99。从上面一个。我们改进了货架算法，并显示了$ 7/2 + sqrt {10}的绝对竞争比率约为6.6623 $，而没有矩形高度的限制。我们的算法还击败了并行作业调度最著名的在线算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号