7
$\begingroup$

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?

$\endgroup$

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.