没有合适的资源?快使用搜索试试~ 我知道了~
首页二维空间有界立方体与超立方体在线打包算法优化
二维空间有界立方体与超立方体在线打包算法优化
0 下载量 175 浏览量
更新于2024-08-26
收藏 264KB PDF 举报
本文探讨的是2空间有界立方体和超立方体包装的在线算法问题。在这个问题中,研究者关注的是将d维(d≥3)的立方体物品(如正方体或超立方体)最小化地装入一序列无限数量的单个面为单位长度的d维立方体容器中。与经典的背包问题有所区别,这里的限制条件是时间进程中,任何时候只能有两个容器是活动的。这意味着在打包过程中,每个物品需要被正交放置,且不能与其他已放置的物品重叠。 算法设计的核心是考虑一个非线性物品输入模式,即每个物品的到来都是独立的,没有关于后续物品的信息。这增加了问题的复杂性,因为算法必须实时决策,适应未知的物品尺寸和数量。研究者借鉴了先前工作中的砖块划分技术,这种方法可能在处理二维情况(如平方砖块)时展现出优势,但如何将其扩展到高维立方体是一个挑战。 在线算法的目标是找到一种策略,能在面对不断到来的物品时动态调整容器使用,以达到最优的总体空间利用率。这种问题在实际应用中有着广泛的意义,例如在数据中心存储、货物装载优化或者虚拟机调度等领域,需要高效利用有限的资源并处理不确定性。 作者Xiaofan Zhao来自北京交通大学计算机与信息技术学院,而Hong Shen则来自中山大学信息科学与技术学院,他们的合作旨在通过理论分析和实验验证,提出适用于这个特定问题的高效在线算法,为未来解决类似的空间限制下的资源分配问题提供新的视角和方法。这篇研究论文对于理解在线算法设计、优化多维空间利用率以及探索适应性策略具有重要的学术价值。
资源详情
资源推荐
On-Line Algorithms for 2-Space Bounded Cube and Hypercube Packing
Xiaofan Zhao
School of Computer and Information Technology
Beijing Jiaotong University
Beijing, China
Email: zxfanfan922@gmail.com
Hong Shen
School of Information Science and Technology
Sun Yat-sen University
Guangzhou, China
Email: shenh3@mail.sysu.edu.cn
Abstract—We consider the problem of packing d-
dimensional cubes into the minimum number of unit cubes
with 2-space bounded, as the generalization of the classic bin
packing problem. Given a sequence of items, each of which
is a d-dimensional (d ≥ 3) hypercube with side length not
greater than 1 and an infinite number of d-dimensional (d ≥ 3)
hypercube bins with unit length on each side, we want to pack
all items in the sequence into a minimum number of bins.
The constraint is that only two bins are active at anytime
during the packing process. Each item should be orthogonally
packed without overlapping with others. Items are given in
an on-line manner which means each item comes without
knowing any information about the subsequent items. We
extend the technique of brick partitioning in paper [1] for
square packing and obtain two results: a three dimensional
box partitioning scheme for cube packing and a d-dimensional
hyperbox partitioning scheme for hypercube packing. We give
a 5.43-competitive algorithm for cube packing and a
32
21
· 2
d
-
competitive algorithm for hypercube packing. To the best of
our knowledge these are the first known results on 2-space
bounded cube and hypercube packing.
Keywords-hypercube packing; 2-bounded space; online algo-
rithm; asymptotic competitive ratio;
I. INTRODUCTION
Bin packing problem is one of the oldest classical prob-
lems in both computer science and combinatorial optimiza-
tion [2], [3]. Since it has been studied for over thirty years,
many variants of this problem have also been well studied.
In this paper, we consider the 2-space bounded on-line d-
dimensional ( d ≥ 3) hypercube packing problem, which is
formulated as follows:
• Input: A list L of items, L =(l
1
,l
2
,...,l
n
). Each
item l
i
is a d-dimensional (d ≥ 3) hypercube (s
1
(l
i
) ×
s
2
(l
i
) × ...× s
d
(l
i
)). I.e., s
k
(l
i
) ∈ (0, 1] is the size of
the k-th dimension. An infinite number of unit-capacity
bins T, each of which is a d-dimensional (d ≥ 3)
hypercube bin with unit length on each side. Items
come online and the packing decision must be made
immediately. When an item l
i
comes, we assign it a
position (x
1
l
i
,x
2
l
i
,...,x
d
l
i
) in the current open bin,
subject to x
k
l
i
+ s
k
(l
j
) ≤ 1, for all 0 <j<iand
1 ≤ k ≤ d.
• Constraint: At any time during the packing, there are
only two open bins. An active bin is closed when there
is not enough space to accommodate the incoming item
and a new bin is open to be the current active bin. Once
a bin is closed, it cannot be used again.
• Goal: Using a minimum number of bins T to hold all
the items in L satisfied the above constraint.
Recently, a lot of work has been done for bounded space
bin packing with less than three active bins. For 1-bounded
space 2D packing, Fujita [4] first gave an on-line algorithm
for rectangle packing in an m×m grid with competitive ratio
of O((log log m)
2
). His main idea is to partition the grid
into different parts and packs items with different size into
corresponding parts. Chin et al. [5] divided rectangular items
into three types and partitioned unit square bin into two parts
which accommodate big and small items respectively. Using
this method, a 8.84-competitive ratio was achieved. The
result was improved to 5.155 by Zhang et al. [6]. For 2-space
bounded 2D packing, Januszewski [1] recently presents a 4-
competitive 2-space bounded 2-dimensional on-line packing
algorithm and an on-line strategy with competitive ratio 3.8
for 2-space bounded square packing by using the technique
of brick partitioning for packing small items. For 1-bounded
space multidimensional bin packing, Zhang et al. [7] gave
an on-line algorithm with competitive ratio 4
d
.
In this paper, we first extend the brick partitioning tech-
nique in paper [1]. Through adding the third dimension, a
brick becomes a box. We propose a box partitioning scheme
for cube packing. Continuously adding new dimensions, a
brick can become a d-dimensional hyperbox. We then pro-
pose a hyperbox partitioning scheme for hypercube packing.
For both problems, we present online algorithms and analyze
the competitive ratio.
II. P
RELIMINARIES
A. Asymptotic Competitive Ratio
The standard measure of on-line algorithm is the asymp-
totic competitive ratio, which is computed by the number
of used bins of an on-line algorithm to the number of used
bins of an optimal offline algorithm. Denote by OP T(L) the
cost of an optimal offline bin packing algorithm, by A(L)
the cost of an on-line approximation algorithm A, where
the cost refers to the number of used bins. The asymptotic
2014 Sixth International Symposium on Parallel Architectures, Algorithms and Programming
2168-3034/14 $31.00 © 2014 IEEE
DOI 10.1109/PAAP.2014.37
87
下载后可阅读完整内容,剩余5页未读,立即下载
weixin_38528180
- 粉丝: 4
- 资源: 942
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功