Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems |
| |
Affiliation: | Decision Sciences, College of Business, The University of Arizona, Tucson, Arizona 85721; and Centre de recherche sur les transports, Université de Montréal, Montréal, Québec, Canada; École Polytechnique, Montréal, Québec, Canada; Mathematics Department, Université de Montréal, Québec, Canada |
| |
Abstract: | In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u1, u2, . . . , uk} together with a "size" vi ≡ v(ui) ∈ Z+, such that vi ≠ vj for i ≠ j, a "frequency" ai ≡ a(ui) ∈ Z+, and a positive integer (shelf length) L ∈ Z+ with the following conditions: (i) L = ∏nj=1pj(pj ∈ Z+ ∀j, pj ≠ pl for j ≠ l) and vi = ∏ j∈Aipj, Ai ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (Ai{⋂kj=1Aj}) ∩ (Al{⋂kj=1Aj}) = ⊘∀i ≠ l. Note that vi|L (divides L) for each i. If for a given m ∈ Z+, ∑ni=1aivi = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b11, b12, . . . , b1m, b21, . . . , bn1, . . . , bnm}⊆ N such that ∑mj=1bij = ai, i = 1, . . . , k, and ∑ki=1bijvi = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|