点击次数：

论文类型：期刊论文

发表时间：2016-08-01

发表刊物：INFORMATION AND COMPUTATION

收录刊物：SCIE、EI、Scopus

卷号：249

页面范围：110-120

ISSN号：0890-5401

关键字：Strip packing; Approximation algorithms; Harmonic algorithms

摘要：In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1.58889 + (sic) on the asymptotic competitive ratio, for any arbitrarily small c > 0. This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed. (C) 2016 Elsevier Inc. All rights reserved.