| REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| Abstract. For n ∈ , we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of the form ℓi ⋄ij ℓj where ⋄ij is one of <,>, or =. In the full information case, ⋄ij is given for all 1 ≤ i, j ≤ k. In the sequential information information case, ⋄ij is given for all 1 < i < k and j = i ± 1. That is, only the relations between the lengths of consecutive intervals are specified. The cyclic information case is an extension of the sequential information case in which the relationship ⋄1k between ℓ1 and ℓk is also given. We show that all three versions of the problem can be solved in time polynomial in k and log n. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||