A linear extension $x_1 x_2 \ldots x_n$ of a partially ordered set (poset) is said to have $k$ jumps if there are $k$ occurrences of consecutive elements that are incomparable with each other -- i.e., $x_i \parallel x_{i+1}$. The jump number of a poset $P$ is the minimum number of jumps in any of its linear extensions. Finding the jump number of a general poset has long been known to be NP-hard [Pulleyblank 1981]. It remains NP-hard for interval posets (posets that admit a representation of elements by intervals in one dimension; an interval that is wholly before another is less than it in the poset).

There are 3/2 approximation algorithms for interval posets [Syslo 1995], and an improvement to 89/60-approximation [Krysztowiak 2013] for the same class of posets.

My question is: what is known about approximating the jump number in the general case? Are there approximation algorithms for the general case, and what approximation ratio do they achieve?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.