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/

[1] P. K. Agarwal, M. van Kreveld, S. Suri, “Label placement by maximum independent set in rectangles”, Comput. Geom., 11 (1998), 209–218 | DOI | MR | Zbl

[2] A. Arnim, C. Higuera, “Computing the jump number on semi-orders is polynomial”, Discrete Appl. Math., 51 (1994), 219–232 | DOI | MR | Zbl

[3] V. Bouchitté, M. Habib, “NP-completeness properties about linear extensions”, Order, 4 (1987), 143–154 | DOI | MR | Zbl

[4] S. Ceroi, “A weighted version of the jump number problem on two-dimensional orders is NP-complete”, Order, 20 (2003), 1–11 | DOI | MR | Zbl

[5] S. Felsner, “A 3/2-approximation algorithm for the jump number of interval orders”, Order, 6 (1990), 325–334 | DOI | MR | Zbl

[6] P. C. Fishburn, Interval orders and interval graphs. A study of partially ordered sets, Wiley, New York, 1985 | MR | Zbl

[7] F. Glover, M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997 | MR

[8] M. Habib, “Comparability invariants”, Orders: Description and Roles, Annals of Discrete Mathematics, 23, eds. M. Pouzet, D. Richard, 1984, 371–386 | MR

[9] M. Held, R. M. Karp, “A dynamic programming approach to sequencing problems”, J. Soc. Ind. Appl. Math., 10 (1962), 196–210 | DOI | MR | Zbl

[10] C. Higuera, L. Nourine, “Drawing and encoding two-dimensional posets”, Theor. Comput. Sci., 175 (1997), 293–308 | DOI | MR | Zbl

[11] C. Iturriaga, Map labeling problems, PhD Thesis, University of Waterloo, 1999

[12] P. Krysztowiak, M. M. Sysło, “An experimental study of approximation algorithms for the jump number problem on interval orders”, Discrete Appl. Math., 2012, submitted

[13] P. Krysztowiak, “An improved approximation ratio for the jump number problem on interval orders”, Theor. Comput. Sci., 513 (2013), 77–84 | DOI | MR | Zbl

[14] P. Krysztowiak, “Improved approximation algorithm for the jump number of interval orders”, Electron. Notes Discrete Math., 40 (2013), 193–198 | DOI

[15] C. McCartin, “An improved algorithm for the jump number problem”, Inform. Process. Lett., 79 (2001), 87–92 | DOI | MR | Zbl

[16] J. Mitas, “Tackling the jump number of interval orders”, Order, 8 (1991), 115–132 | DOI | MR | Zbl

[17] A. Ngom, “Genetic algorithm for the jump number scheduling problem”, Order, 15 (1998), 59–73 | DOI | MR | Zbl

[18] W. R. Pulleyblank, “On minimizing setups in precedence-constrained scheduling”, Report No. 81185 – OR (unpublished), May, 1981

[19] I. Rival, “Optimal linear extensions by interchanging chains”, Proc. Am. Math. Soc., 89 (1983), 387–394 | DOI | MR | Zbl

[20] J. Spinrad, J. Valdes, “Recognition and isomorphism of two dimensional partial orders”, Automata, Languages and Programming, LNCS, 154, 1983, 676–686 | MR | Zbl

[21] M. M. Sysło, “A graph-theoretic approach to the jump-number problem”, Graphs and Orders, ed. I. Rival, D. Reidel, Dodrecht, 1985, 185–215 | MR

[22] M. M. Sysło, “Minimizing the jump number for partially ordered sets: a graph-theoretic approach”, Order, 1 (1984), 7–19 | DOI | MR | Zbl

[23] M. M. Sysło, “Minimizing the jump number for partially-ordered sets: a graph-theoretic approach, II”, Discrete Math., 63 (1987), 279–295 | DOI | MR | Zbl

[24] M. M. Sysło, “An algorithm for solving the jump number problem”, Discrete Math., 72 (1988), 337–346 | DOI | MR | Zbl

[25] M. M. Sysło, “The jump number problem on interval orders: A 3/2 approximation algorithm”, Discrete Math., 144 (1995), 119–130 | DOI | MR | Zbl

[26] M. H. El-Zahar, J. H. Schmerl, “On the size of jump-critical ordered sets”, Order, 1 (1984), 3–5 | DOI | MR | Zbl

[27] M. H. El-Zahar, I. Rival, “Examples of jump-critical ordered sets”, SIAM J. Algebr. Discrete Meth., 6 (1985), 713–720 | DOI | MR | Zbl

[28] M. H. El-Zahar, “On jump-critical posets with jump-number equal to width”, Order, 17 (2000), 93–101 | DOI | MR | Zbl