Indexed by:期刊论文

Date of Publication:2016-08-01

Journal:INFORMATION AND COMPUTATION

Included Journals:SCIE、EI、Scopus

Volume:249

Page Number:110-120

ISSN No.:0890-5401

Key Words:Strip packing; Approximation algorithms; Harmonic algorithms

Abstract: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.