2021/11/08 by Csaba Bíró, Biró, Csaba, Israel R. Curbelo +1
Computer Science · #Algorithms and Data Compression #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2111.04790
openalex publication_date 2021/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains in the partition. The on-line chain partitioning problem involves finding the minimal number of chains needed by an optimal on-line algorithm. Chrobak and Ślusarek considered variants of the on-line chain partitioning problem in which the elements are presented as intervals and intersecting intervals are incomparable. 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 this algorithm is optimal. They also considered the problem restricted to intervals of 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 optimal algorithm exists. In this paper, we improve upon previously known bounds and show that any on-line algorithm can be forced to use \lceil(3)/(2)w\rceil chains to partition a semi-order presented in the form of its unit-interval representation. As a consequence, we completely solve the problem for w=3.