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 language | English (US) |
---|---|
Pages (from-to) | 145-149 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 31 |
Issue number | 3 |
DOIs | |
State | Published - May 8 1989 |
Externally published | Yes |
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