Probabilistic analysis of a bin covering algorithm

Sunan Han, Dawei Hong, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In the bin covering problem we are asked to pack a list X(n) = (x1,x2, ... , xn) of n items, each with size no larger than one, into the maximum number of bins such that the sum of the sizes of the items in each bin is at least one. In this article we analyze the asymptotic average-case behavior of the Iterated-Lowest-Fit-Decreasing(ILFD) algorithm proposed by Assmann et al. Let OPT(X(n)) denote the maximum number of bins that can be covered by X(n) and let ILFD(X(n)) denote the number of bins covered by the ILFD algorithm. Assuming that X(n) is a random sample from an arbitrary probability measure μ over [0, 1], we show the existence of a constant d(μ) and a constructible sequence {Ξ(n) ∈ [0, 1]n: n ≥ 1} such that |(ILFD(Ξ(n))/n) - d(μ;)| ≤ 1/n and limn→∞ (ILFD(X(n))/n) = d(μ), almost surely. Since (ILFD(X(n))/n) always lies in [0, 1], it follows that limn→∞. (E[ILFD(X(n))]/n) = d(μ) as well. We also show that the expected values of the ratio rILFD(X(n)) = OPT(X(n))/ILFD(X(n)), over all possible probability measures for X(n), lie in [1, 4/3], the same range as the deterministic case.

Original languageEnglish (US)
Pages (from-to)193-199
Number of pages7
JournalOperations Research Letters
Volume18
Issue number4
DOIs
StatePublished - Feb 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Keywords

  • Average-case analysis
  • Bin covering
  • Bin packing
  • Heuristic
  • Np-hard

Fingerprint

Dive into the research topics of 'Probabilistic analysis of a bin covering algorithm'. Together they form a unique fingerprint.

Cite this