A subexponential upper bound for the on-line chain partitioning problem

作者：Bosek Bartlomiej^*; Krawczyk Tomasz

来源：Combinatorica, 2015, 35(1): 1-38.

DOI：10.1007/s00493-014-2908-7

The main question in the on-line chain partitioning problem is to decide whether there exists an on-line algorithm that partitions posets of width at most w into polynomial number of chains - see Trotter's chapter Partially ordered sets in the Handbook of Combinatorics. So far the best known on-line algorithm of Kierstead used at most (5 (w) - 1)/4 chains; on the other hand Szemer,di proved that any on-line algorithm requires at least chains. These results were obtained in the early eighties and since then no progress in the general case has been done.
We provide an on-line algorithm that partitions posets of width w into at most w (13logw) chains. This yields the first subexponential upper bound for the on-line chain partitioning problem.

• 出版日期2015-2