A tabu search approach to the jump number problem

Abstract

We consider algorithmics for the jump number problem, which is
to generate a linear extension of a given poset, minimizing the number
of incomparable adjacent pairs. Since this problem is NP-hard
on interval orders and open on two-dimensional posets,
approximation algorithms or
fast exact algorithms are in demand.

In this paper, succeeding from the work of the second named author on
semi-strongly greedy
linear extensions, we develop a metaheuristic algorithm to approximate
the jump number with the tabu search paradigm. To benchmark
the proposed procedure, we infer from the previous work of Mitas
[Order 8 (1991), 115--132]
a new fast exact algorithm for the case of
interval orders, and from the results of Ceroi
[Order 20 (2003), 1--11]
a lower bound
for the jump number of two-dimensional posets.
Moreover, by other techniques we prove
an approximation ratio of \(n / \log\log n\) for 2D orders.