First-Fit Algorithm for the On-Line Chain Partitioning Problem
Tytuł:
First-Fit Algorithm for the On-Line Chain Partitioning Problem
Czasopismo:
Rok:
2010
Opis:
We consider a problem of partitioning a partially ordered set into chains by first-fit algorithm. In general this algorithm uses arbitrarily many chains on a class of bounded width posets. In this paper we prove that First-Fit uses at most 3tw(2) chains to partition any poset of width w which does not induce two incomparable chains of height t. In this way we get a wide class of posets with polynomial bound for the on-line chain partitioning problem.
Strony:
1992-1999
Tom (seria wydawnicza):
23(4)
Numer DOI:
10.1137/090753863
Link:
http://dx.doi.org/10.1137/090753863
Mathscinet link:
http://www.ams.org/mathscinet-getitem?mr=2594967
DBLP link:
https://dblp.org/rec/journals/siamdm/BosekKS10
Access:
ZAMKNIĘTY