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