On a dual version of the one-dimensional bin packing problem

S. F. Assmann, D. S. Johnson, D. J. Kleitman, J. Y.T. Leung

Research output: Contribution to journalArticlepeer-review

139 Scopus citations

Abstract

The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of 1 2, 2 3, and 3 4 the optimal number, at running time costs of O(n), O(nlogn), and O(nlog2n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items.

Original languageEnglish (US)
Pages (from-to)502-525
Number of pages24
JournalJournal of Algorithms
Volume5
Issue number4
DOIs
StatePublished - Dec 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'On a dual version of the one-dimensional bin packing problem'. Together they form a unique fingerprint.

Cite this