Indexed by:期刊论文

Date of Publication:2013-10-28

Journal:THEORETICAL COMPUTER SCIENCE

Included Journals:SCIE、EI、Scopus

Volume:510

Page Number:13-61

ISSN No.:0304-3975

Key Words:First Fit Decreasing; Tight bound

Abstract:First Fit Decreasing is a classical bin-packing algorithm: the items are ordered by non-increasing size, and then in this order the next item is always packed into the first bin where it fits. For an instance L let FFD(L) and OPT(L) denote the number of bins used by algorithm FFD and by an optimal algorithm, respectively. In this paper we give the first complete proof of the inequality
   FFD(L) <= 11/9 . OPT(L) + 6/9.
   This result is best possible, as was shown earlier by Dosa (2007) [3]. The asymptotic coefficient 11/9 was proved already in 1973 by Johnson, but the tight bound of the additive constant was an open question for four decades. (C) 2013 Elsevier B.V. All rights reserved.