Name
Abstract | ||
|---|---|---|
It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w, then Bosek, Krawczyk, and Szczypka [SIAM J. Discrete Math., 23 (2010), pp. 1992-1999], proved an upper bound of ckw(2) on the number of chains used by First-Fit for some constant c, while Joret and Milans [Order, 28 (2011), pp. 455-464] gave one of ck(2)w. In this paper we prove an upper bound of the form ckw. This is most possible up to the value of c. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/110855806 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
First-Fit,on-line chain partition | Discrete mathematics,Combinatorics,Of the form,Upper and lower bounds,Mathematics,Partially ordered set | Journal |
Volume | Issue | ISSN |
26 | 3 | 0895-4801 |
Citations | PageRank | References |
5 | 0.53 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vida Dujmovic | 1 | 416 | 43.34 |
| Gwenaël Joret | 2 | 196 | 28.64 |
| David R. Wood | 3 | 1073 | 96.22 |