| Realizing Partitions Respecting Full and Partial Order Information Abstract (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| For n ∈ 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 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. Preprint submitted to JDA i\j 1 2 3 4 1 = = < < 2 = = < < 3>> => 4>> < = Fig. 1. A comparison matrix for the full information case. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||