Geodesic
A tabu search approach to the jump number problem
Algebra and discrete mathematics, Tome 20 (2015) no. 1, pp. 89-114

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: graph theory, poset, jump number, combinatorial optimization, tabu search. 
@article{ADM_2015_20_1_a7,
     author = {Przemys{\l}aw Krysztowiak and Maciej M. Sys{\l}o},
     title = {A tabu search approach to the jump number problem},
     journal = {Algebra and discrete mathematics},
     pages = {89--114},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2015_20_1_a7/}
}
TY  - JOUR
AU  - Przemysław Krysztowiak
AU  - Maciej M. Sysło
TI  - A tabu search approach to the jump number problem
JO  - Algebra and discrete mathematics
PY  - 2015
SP  - 89
EP  - 114
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2015_20_1_a7/
LA  - en
ID  - ADM_2015_20_1_a7
ER  - 
%0 Journal Article
%A Przemysław Krysztowiak
%A Maciej M. Sysło
%T A tabu search approach to the jump number problem
%J Algebra and discrete mathematics
%D 2015
%P 89-114
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2015_20_1_a7/
%G en
%F ADM_2015_20_1_a7
Przemysław Krysztowiak; Maciej M. Sysło. A tabu search approach to the jump number problem. Algebra and discrete mathematics, Tome 20 (2015) no. 1, pp. 89-114. http://geodesic.mathdoc.fr/item/ADM_2015_20_1_a7/