English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

An on-line chain partitioning algorithm receives a poset, one element at atime, and irrevocably assigns the element to one of the chains in thepartition. The on-line chain partitioning problem involves finding the minimalnumber of chains needed by an optimal on-line algorithm. Chrobak and \'Slusarekconsidered variants of the on-line chain partitioning problem in which theelements are presented as intervals and intersecting intervals areincomparable. They constructed an on-line algorithm which uses at most $3w-2$chains, where $w$ is the width of the interval order, and showed that thisalgorithm is optimal. They also considered the problem restricted to intervalsof unit-length and while they showed that first-fit needs at most $2w-1$chains, over $30$ years later, it remains unknown whether a more optimalalgorithm exists. In this paper, we improve upon previously known bounds andshow that any on-line algorithm can be forced to use $\lceil\frac{3}{2}w\rceil$chains to partition a semi-order presented in the form of its unit-intervalrepresentation. As a consequence, we completely solve the problem for $w=3$.

Improved lower bound on the on-line chain partitioning of semi-orders with representation