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

Csaba Biró, Israel R. Curbelo

Research output: Contribution to journalArticlepeer-review

Abstract

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 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 this is an optimal algorithm. In this paper, we improve upon previously known bounds and show that any on-line algorithm can be forced to use [Formula presented] chains to partition an order presented in the form of its unit interval representation. As a consequence, we completely solve the problem for w=3. Lastly, we show that loosening the restriction from unit intervals to proper intervals in the bandwidth variant allows us to improve the lower bound by w/3.

Original languageEnglish
Article number113656
JournalDiscrete Mathematics
Volume346
Issue number12
DOIs
StatePublished - Dec 2023

Keywords

  • Bandwidth
  • Chain partitioning
  • On-line algorithm
  • Semiorder

Fingerprint

Dive into the research topics of 'Improved lower bound on the on-line chain partitioning of semi-orders with representation'. Together they form a unique fingerprint.

Cite this