Title | ||
---|---|---|
Packing Shelves With Items That Divide The Shelves' Length: A Case Of A Universal Number Partition Problem |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1142/S1793830910000565 | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS |
Keywords | Field | DocType |
Universal Number Partition, divisibility and packing | Integer,Partition problem,Discrete mathematics,Combinatorics,Packing problems,Square packing in a square,Divisor function,Set packing,Packing dimension,Divisor,Mathematics | Journal |
Volume | Issue | ISSN |
2 | 2 | 1793-8309 |
Citations | PageRank | References |
1 | 0.43 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Moshe Dror | 1 | 574 | 64.77 |
James B. Orlin | 2 | 2812 | 319.77 |
MICHAEL ZHU | 3 | 174 | 8.49 |