Variants of Online Chain Partition Problem of Posets

Online chain partitioning problem of posets is open for at least last 15 years. The best known online algorithm uses 5w−14 chains to cover width w posets. A variant of this problem considering only upgrowing posets, i.e. online posets in which every, new point is maximal at the moment it arrives, has been solved by Felsner [S. Felsner On-line chain partitions of orders, Theoretical Computer Science 175 (1997) 283-292]. He presented an algorithm using (w+12) chains to cover posets of width w. Moreover, he proved that this is an optimal solution. We are interested in special class of posets, namely the interval posets. For this class we present an algorithm using 2w−1 chains for width w and we prove that there is no better algorithm. In [S. Felsner On-line chain partitions of orders, Theoretical Computer Science 175 (1997) 283-292] Felsner also considers an adaptive chain covering problem for upgrowing posets. We are able to show a lowerbound for this problem to be (2−ɛ)⋅w for width w posets.