The Sub-exponential Upper Bound for On-Line Chain Partitioning

Tytuł rozdziału:
The Sub-exponential Upper Bound for On-Line Chain Partitioning
Tytuł książki:
51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA
Wydawnictwo:
Institute of Electrical and Electronics Engineers (IEEE)
Rok:
2010

Opis:
The main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line 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 Kier stead used at most (5^w-1)/4 chains, on the other hand Szemer'{e}di proved that any on-line algorithm requires at least inom{w+1}{2} chains. These results were obtained in the

Strony:
347-354