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\{{n-ary intersection}kj=1Aj}) ⋂ (Al\{{n-ary intersection}kj=1Aj}) = {circled division slash}∀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.
Original language | English (US) |
---|---|
Pages (from-to) | 216-229 |
Number of pages | 14 |
Journal | Journal of Complexity |
Volume | 10 |
Issue number | 2 |
DOIs | |
State | Published - Jun 1994 |
ASJC Scopus subject areas
- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- Mathematics(all)
- Control and Optimization
- Applied Mathematics