The jump number problem on interval orders: A 32 approximation algorithm

AbstractIn this paper, we consider the jump number problem on interval orders and use arc-diagram representations of posets to provide an approximation algorithm for the problem in this case. First, a complete characterization of arc-diagrams of interval orders is presented. Then, based on the properties of such representations, it is shown that semi-strongly greedy linear extensions (introduced by the author in 1987), in the case of interval orders are at most 50% worse than optimal linear extensions. This shows also that the pseudo-polynomial time backtracking algorithm for solving the jump number problem on arbitrary posets (Syslo, 1988) is a linear-time 32-approximation algorithm when the problem is restricted to interval orders. Moreover, in several cases the proposed algorithm proves the optimality of the solutions generated