In the Two-dimensional Bin Packing (2BP) problem, we are given a set of rectangles of height and width at most one and our goal is to find an axis-aligned nonoverlapping packing of these rectangles into the minimum number of unit square bins. The problem admits no APTAS and the current best approximation ratio is $1.406$ by Bansal and Khan [SODA'14]. A well-studied variant of the problem is Guillotine Two-dimensional Bin Packing (G2BP), where all rectangles must be packed in such a way that every rectangle in the packing can be obtained by recursively applying a sequence of end-to-end axis-parallel cuts, also called guillotine cuts. Bansal, Lodi, and Sviridenko [FOCS'05] obtained an APTAS for this problem. Let $\lambda$ be the smallest constant such that for every set $I$ of items, the number of bins in the optimal solution to G2BP for $I$ is upper bounded by $\lambda\operatorname{opt}(I) + c$, where $\operatorname{opt}(I)$ is the number of bins in the optimal solution to 2BP for $I$ and $c$ is a constant. It is known that $4/3 \le \lambda \le 1.692$. Bansal and Khan [SODA'14] conjectured that $\lambda = 4/3$. The conjecture, if true, will imply a $(4/3+\varepsilon)$-approximation algorithm for 2BP. According to convention, for a given constant $\delta>0$, a rectangle is large if both its height and width are at least $\delta$, and otherwise it is called skewed. We make progress towards the conjecture by showing $\lambda = 4/3$ for skewed instance, i.e., when all input rectangles are skewed. Even for this case, the previous best upper bound on $\lambda$ was roughly 1.692. We also give an APTAS for 2BP for skewed instance, though general 2BP does not admit an APTAS.


翻译:在二维的 Bin 包装 (2BP) 问题中, 我们得到的是一组以高度和宽度为单位的直径矩形。 最多一个, 我们的目标是找到一个以轴为主的不重叠包装这些正方形的最小数量 。 问题没有接受 APTAS, 而目前的最佳近似比率是 Bansal 和 Khan [SODA'14] 的 1.406 美元。 问题的一个得到很好研究的变式是 吉洛丁 双维本包( G2BP) 。 所有正方块的平面矩形必须以这样的方式打包, 使每个正方块的正方块 $ 2. 0. 3 美元 的正方格可以再次使用端对端轴轴轴轴轴的切分解 。 当 以美元为正值的平面的平面的平面的平面是 。 以美元平面的平面的平面的平面的平面的平面的平面是 。 当 以美元平面的平面的平面的平面的平面的平面的平面的平面的平面是 。

0
下载
关闭预览

相关内容

Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【课程推荐】 深度学习中的几何(Geometry of Deep Learning)
专知会员服务
57+阅读 · 2019年11月10日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
经典回顾 | Collaborative Metric Learning
机器学习与推荐算法
6+阅读 · 2020年9月18日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
小白都能看懂的神经网络入门,快收下吧~
码农翻身
3+阅读 · 2018年1月4日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月1日
Arxiv
0+阅读 · 2021年6月30日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关VIP内容
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【课程推荐】 深度学习中的几何(Geometry of Deep Learning)
专知会员服务
57+阅读 · 2019年11月10日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
相关资讯
经典回顾 | Collaborative Metric Learning
机器学习与推荐算法
6+阅读 · 2020年9月18日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
小白都能看懂的神经网络入门,快收下吧~
码农翻身
3+阅读 · 2018年1月4日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员