TY - JOUR

T1 - Packing shelves with items that divide the shelves' length

T2 - A case of a universal number partition problem

AU - Dror, Moshe

AU - Orlin, James B.

AU - Zhu, Michael

N1 - Publisher Copyright:
© 2010 World Scientific Publishing Company.

PY - 2010/6/1

Y1 - 2010/6/1

N2 - This note examines the likelihood of packing two identical one dimensional shelves of integer length L by items whose individual lengths are divisors of L, given that their combined length sums-up to 2L. We compute the number of packing failures and packing successes for integer shelve lengths L, 1 ≤ L ≤ 1000, by implementing a dynamic programming scheme using a problem specific "boundedness property". The computational results indicate that the likelihood of a packing failure is very rare. We observe that the existence of packing failures is tied to the number of divisors of L and prove that the number of divisors has to be at least 8 for a packing failure to exist.

AB - This note examines the likelihood of packing two identical one dimensional shelves of integer length L by items whose individual lengths are divisors of L, given that their combined length sums-up to 2L. We compute the number of packing failures and packing successes for integer shelve lengths L, 1 ≤ L ≤ 1000, by implementing a dynamic programming scheme using a problem specific "boundedness property". The computational results indicate that the likelihood of a packing failure is very rare. We observe that the existence of packing failures is tied to the number of divisors of L and prove that the number of divisors has to be at least 8 for a packing failure to exist.

KW - Universal Number Partition

KW - divisibility and packing

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

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

U2 - 10.1142/S1793830910000565

DO - 10.1142/S1793830910000565

M3 - Article

AN - SCOPUS:84858796820

SN - 1793-8309

VL - 2

SP - 189

EP - 198

JO - Discrete Mathematics, Algorithms and Applications

JF - Discrete Mathematics, Algorithms and Applications

IS - 2

ER -