Realizing partitions respecting full and partial order information

Written with Erik D. Demaine, Danny Krizanc, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides

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 liij 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