Bin packing with restricted piece sizes

Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

Coffman et al. have recently shown that a large number of bin-packing problems can be solved in polynomial time if the piece sizes are drawn from the power set of an arbitrary positive integer q (i.e., the piece sizes are drawn from the set {1, q, q2, q3,...}). In this article we show that these problems remain NP-hard if the piece sizes are drawn from the power set of an arbitrary positive rational number r. We also show that the running time of the ε{lunate}-approximation scheme recently proposed by Hochbaum and Shmoys for the multiprocessor scheduling problem can be reduced from O((n/ε{lunate})exp(1/ε{lunate})2) time to O(n/ε{lunate})exp((1/ε{lunate})log(1/ε{lunate})) time.

Original languageEnglish (US)
Pages (from-to)145-149
Number of pages5
JournalInformation Processing Letters
Volume31
Issue number3
DOIs
StatePublished - May 8 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Bin-packing problems
  • multiprocessor scheduling
  • strongly NP-hard
  • ε{lunate}-approximation algorithms
  • ε{lunate}-approximation scheme

Fingerprint

Dive into the research topics of 'Bin packing with restricted piece sizes'. Together they form a unique fingerprint.

Cite this