Technical Report 220-1989
- Title
- A 3/2-Approximation Algorithm for the Jump Number of Interval Orders
- Author
- Publication
- ORDER, vol. 6, 1990, pp. 325-334
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
The jump number of a partial order P is the minimum number of incomparable adjacent pairs in some linear extension of P. The jump number is known to be NP-hard in general. However some particular classes of posets admit easy calculation of the jump number. The complexity status for interval orders still remains unknown. Here we present an algorithm that, given an interval order P, generates a linear extension Lambda, whose jump number is less than frac32 times the jump number of P.