A 3/2-approximation algorithm for the jump number of interval orders (Q921022)

Let P be a (partially) ordered finite set. A pair of two consecutive elements \(x_ i<x_{i+1}\) of a linear extension L of P is called a jump if \(x_ i\) is incomparable to \(x_{i+1}\) in P. The number of all jumps of L is denoted by \(s_ p(L)\). The minimum number of \(s_ P(L)\) is called the jump number s(P) of P \((s(P)=\min \{a_ P(L):\) L is a linear extension of \(P\}\)). An optimal linear extension L of P has the property \(s(P)=s_ P(L).\) In this paper some algorithms constructing linear extensions are developed, especially for interval orders, which are ordered sets P whose elements are in a one-to-one correspondence with intervals on the real axis \((x\leftrightarrow I_ x)\) such that \(x<_ Py\) iff sup \(I_ x\leq \inf I_ y\). For an interval order P a linear extension \(\Lambda\) is constructed with \(s_ P(\Lambda)\leq (3/2)s(P)\).