Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

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 = {u₁, u₂, …, u_k} together with a “size” v_i ∈ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ∈ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, …, n} for i = 1, …, n; (ii) (A_i\{{n-ary intersection}^k_j=1A_j}) ⋂ (A_l\{{n-ary intersection}^k_j=1A_j}) = {circled division slash}∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = 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 {b₁₁, b₁₂, …, b_1m, b₂₁, …, b_n1, …, b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, …, k, and ∑^k_i=1b_ijv_i = 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.