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

Speaker(s)

Bartlomiej Bosek i Tomasz Krawczyk

Affiliation

Uniwersytet Jagielloński

Date

Nov. 25, 2010, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---