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 integersnandk, we consider the problem of partitioning the interval [0,n) intoksubintervals of positive integer lengthsl_{1},...,lsuch that the lengths satisfy a set of simple constraints of the form_{k}l, where_{i}◊_{ij}l_{j}◊is one of <, >, or =. In the_{ij}full informationcase,◊is given for all_{ij}iandj. In thesequential informationcase,◊is given for all 1<_{ij}i<kandj=i±1. That is, only the relations between the lengths of consecutive intervals are specified. Thecyclic informationcase is an extension of the sequential information case in which the relationship ◊_{1k}between 1 andkis also given. We show that all three versions of the problem can be solved in time polynomial inkand logn.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012