Name
Title | ||
|---|---|---|
Utilizing shelve slots: sufficiency conditions for some easy instances of hard problems |
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 = { u 1 , u 2 , . . . , 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 = ∏ n j =1 p j ( p j ∈ Z + ∀ j , p j ≠ p l for j ≠ l ) and v i = ∏ j ∈ A i p j , A i ⊆ {l, 2, . . . , n } for i = 1, . . . , n ; (ii) ( A i \{⋂ k j =1 A j }) ∩ ( A l \{⋂ k j =1 A j }) = ⊘∀ i ≠ l . Note that v i | L (divides L ) for each i . If for a given m ∈ Z + , ∑ n i =1 a i v 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 11 , b 12 , . . . , b 1 m , b 21 , . . . , b n 1 , . . . , b nm }⊆ N such that ∑ m j =1 b ij = a i , i = 1, . . . , k , and ∑ k i =1 b ij v 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. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1006/jcom.1994.1010 | J. Complexity |
Keywords | DocType | Volume |
sufficiency condition,hard problem,easy instance,shelve slot | Journal | 10 |
Issue | ISSN | Citations |
2 | Journal of Complexity | 2 |
PageRank | References | Authors |
0.80 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moshe Dror | 1 | 574 | 64.77 |
| Benjamin T. Smith | 2 | 2 | 0.80 |
| Martin Trudeau | 3 | 61 | 5.19 |