Bin packing with restricted piece sizes

Joseph Leung

Research output: Contribution to journalArticle

15 Citations (Scopus)

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

Fingerprint

Bin Packing
Bins
Computational complexity
Power set
Scheduling
Polynomials
Q-integers
Multiprocessor Scheduling
Bin Packing Problem
Arbitrary
NP-hard Problems
Approximation Scheme
Scheduling Problem
Polynomial time

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Cite this

Leung, Joseph. / Bin packing with restricted piece sizes. In: Information Processing Letters. 1989 ; Vol. 31, No. 3. pp. 145-149.
@article{b298eaa6e1c445cc94832be2e58ae42e,
title = "Bin packing with restricted piece sizes",
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.",
author = "Joseph Leung",
year = "1989",
month = "5",
day = "8",
doi = "https://doi.org/10.1016/0020-0190(89)90223-8",
language = "English (US)",
volume = "31",
pages = "145--149",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "3",

}

Bin packing with restricted piece sizes. / Leung, Joseph.

In: Information Processing Letters, Vol. 31, No. 3, 08.05.1989, p. 145-149.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Bin packing with restricted piece sizes

AU - Leung, Joseph

PY - 1989/5/8

Y1 - 1989/5/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024964562&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024964562&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/0020-0190(89)90223-8

DO - https://doi.org/10.1016/0020-0190(89)90223-8

M3 - Article

VL - 31

SP - 145

EP - 149

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 3

ER -