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 language | English |
---|---|
Article number | 113656 |
Journal | Discrete Mathematics |
Volume | 346 |
Issue number | 12 |
DOIs | |
State | Published - Dec 2023 |
Keywords
- Bandwidth
- Chain partitioning
- On-line algorithm
- Semiorder