Geodesic
An easy subexponential bound for online chain partitioning
Bartłomiej Bosek1 ; H. A. Kierstead2 ; Tomasz Krawczyk1 ; Grzegorz Matecki1 ; Matthew E. Smith2
1Jagiellonian University in Kraków
2Arizona State University
The electronic journal of combinatorics, Tome 25 (2018) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Bosek and Krawczyk exhibited an online algorithm for partitioning an online poset of width $w$ into $w^{14\lg w}$ chains. We improve this to $w^{6.5 \lg w + 7}$ with a simpler and shorter proof by combining the work of Bosek & Krawczyk with work of Kierstead & Smith on First-Fit chain partitioning of ladder-free posets. We also provide examples illustrating the limits of our approach.
DOI : 10.37236/7231
Classification : 06A07, 05C15, 68W27
Mots-clés : partially ordered set, poset, first-fit, online chain partition, ladder, regular poset

Bartłomiej Bosek  1   ; H. A. Kierstead  2   ; Tomasz Krawczyk  1   ; Grzegorz Matecki  1   ; Matthew E. Smith  2

1 Jagiellonian University in Kraków
2 Arizona State University 
@article{10_37236_7231,
     author = {Bart{\l}omiej Bosek and H. A. Kierstead and Tomasz Krawczyk and Grzegorz Matecki and Matthew E. Smith},
     title = {An easy subexponential bound for online chain partitioning},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/7231},
     zbl = {1390.06001},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7231/}
}
TY  - JOUR
AU  - Bartłomiej Bosek
AU  - H. A. Kierstead
AU  - Tomasz Krawczyk
AU  - Grzegorz Matecki
AU  - Matthew E. Smith
TI  - An easy subexponential bound for online chain partitioning
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7231/
DO  - 10.37236/7231
ID  - 10_37236_7231
ER  - 
%0 Journal Article
%A Bartłomiej Bosek
%A H. A. Kierstead
%A Tomasz Krawczyk
%A Grzegorz Matecki
%A Matthew E. Smith
%T An easy subexponential bound for online chain partitioning
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7231/
%R 10.37236/7231
%F 10_37236_7231
Bartłomiej Bosek; H. A. Kierstead; Tomasz Krawczyk; Grzegorz Matecki; Matthew E. Smith. An easy subexponential bound for online chain partitioning. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7231

Cité par Sources :