A tabu search approach to the jump number problem
We consider algorithmics for the jump numberproblem, which is to generate a linear extension of a given poset,minimizing the number of incomparable adjacent pairs. Since thisproblem is NP-hard on interval orders and open on two-dimensionalposets, approximation algorithms or fast exact algorithms are...
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2015 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2015
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/158002 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | A tabu search approach to the jump number problem / P. Krysztowiak, M.M. Sysło // Algebra and Discrete Mathematics. — 2015. — Vol. 20, № 1. — С. 89–114. — Бібліогр.: 28 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862558245136105472 |
|---|---|
| author | Krysztowiak, P. Sysło, M.M. |
| author_facet | Krysztowiak, P. Sysło, M.M. |
| citation_txt | A tabu search approach to the jump number problem / P. Krysztowiak, M.M. Sysło // Algebra and Discrete Mathematics. — 2015. — Vol. 20, № 1. — С. 89–114. — Бібліогр.: 28 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | We consider algorithmics for the jump numberproblem, which is to generate a linear extension of a given poset,minimizing the number of incomparable adjacent pairs. Since thisproblem is NP-hard on interval orders and open on two-dimensionalposets, approximation algorithms or fast exact algorithms are indemand.In this paper, succeeding from the work of the second namedauthor on semi-strongly greedy linear extensions, we develop ametaheuristic algorithm to approximate the jump number with thetabu search paradigm. To benchmark the proposed procedure, weinfer from the previous work of Mitas [Order 8 (1991), 115–132] anew fast exact algorithm for the case of interval orders, and from theresults of Ceroi [Order 20 (2003), 1–11] a lower bound for the jumpnumber of two-dimensional posets. Moreover, by other techniqueswe prove an approximation ratio ofn/log lognfor 2D orders.
|
| first_indexed | 2025-11-25T22:45:11Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-158002 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-11-25T22:45:11Z |
| publishDate | 2015 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Krysztowiak, P. Sysło, M.M. 2019-06-22T12:15:04Z 2019-06-22T12:15:04Z 2015 A tabu search approach to the jump number problem / P. Krysztowiak, M.M. Sysło // Algebra and Discrete Mathematics. — 2015. — Vol. 20, № 1. — С. 89–114. — Бібліогр.: 28 назв. — англ. 1726-3255 2010 MSC:90C27, 90C59. https://nasplib.isofts.kiev.ua/handle/123456789/158002 We consider algorithmics for the jump numberproblem, which is to generate a linear extension of a given poset,minimizing the number of incomparable adjacent pairs. Since thisproblem is NP-hard on interval orders and open on two-dimensionalposets, approximation algorithms or fast exact algorithms are indemand.In this paper, succeeding from the work of the second namedauthor on semi-strongly greedy linear extensions, we develop ametaheuristic algorithm to approximate the jump number with thetabu search paradigm. To benchmark the proposed procedure, weinfer from the previous work of Mitas [Order 8 (1991), 115–132] anew fast exact algorithm for the case of interval orders, and from theresults of Ceroi [Order 20 (2003), 1–11] a lower bound for the jumpnumber of two-dimensional posets. Moreover, by other techniqueswe prove an approximation ratio ofn/log lognfor 2D orders. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics A tabu search approach to the jump number problem Article published earlier |
| spellingShingle | A tabu search approach to the jump number problem Krysztowiak, P. Sysło, M.M. |
| title | A tabu search approach to the jump number problem |
| title_full | A tabu search approach to the jump number problem |
| title_fullStr | A tabu search approach to the jump number problem |
| title_full_unstemmed | A tabu search approach to the jump number problem |
| title_short | A tabu search approach to the jump number problem |
| title_sort | tabu search approach to the jump number problem |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/158002 |
| work_keys_str_mv | AT krysztowiakp atabusearchapproachtothejumpnumberproblem AT sysłomm atabusearchapproachtothejumpnumberproblem AT krysztowiakp tabusearchapproachtothejumpnumberproblem AT sysłomm tabusearchapproachtothejumpnumberproblem |