Journal of Discrete Algorithms 6:51-58, 2008.
(Special issue of invited papers from the 16th Australasian Workshop on Combinatorial Algorithms)
Proceedings of the 16th Australasian Workshop on Combinatorial Algorithms, 2005.
Abstract:
For integers n and k, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths l1,...,lk such that the lengths satisfy a set of simple constraints of the form li ◊ij lj, where ◊ij is one of <, >, or =. In the full information case, ◊ij is given for all i and j. 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.
Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012