The sub-exponential upper bound for the on-line chain partitioning problem

One of the important models for scheduling is based on partially ordered sets. In this model the points represent the incoming tasks and the order reflects cause-effect relation between tasks. The algorithmic problem which arises in this model is to divide on-line the set of points of the poset into chains: the tasks from a common chain will be executed by a single device. Keeping this constraint, which asserts the optimality of the execution time, the scheduler tries to minimize the number of devices needed. It naturally leads to the on-line chain partitioning problem.

So far the best known on-line algorithm partitioning a poset of width $w$ is the one of Kierstead and uses at most $(5^w-1)/4$ chains; on the other hand Szemer\'{e}di proved that any such algorithm requires at least $\binom{w+1}{2}$ chains. These results were obtained in the early 1980's and since then no progress has been done. Following Trotter's chapter \emph{Partially ordered sets} of the \emph{Handbook of Combinatorics}, the main problem here is to narrow these bounds and in particular to decide whether there exists an on-line algorithm that partitions posets of width at most $w$ into polynomial number of chains.

In this paper we provide an on-line algorithm that partitions posets of width $w$ into at most $w^{14\log{w}}$ chains. This yields the first sub-exponential upper bound for the on-line chain partitioning problem.