A tabu search approach to the jump number problem

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...

Full description

Saved in:
Bibliographic Details
Date:2015
Main Authors: Krysztowiak, P., Sysło, M.M.
Format: Article
Language:English
Published: Інститут прикладної математики і механіки НАН України 2015
Series:Algebra and Discrete Mathematics
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/158002
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this: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
id nasplib_isofts_kiev_ua-123456789-158002
record_format dspace
fulltext
spelling nasplib_isofts_kiev_ua-123456789-1580022025-02-09T11:56:35Z A tabu search approach to the jump number problem Krysztowiak, P. Sysło, M.M. 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. 2015 Article 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 en Algebra and Discrete Mathematics application/pdf Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
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.
format Article
author Krysztowiak, P.
Sysło, M.M.
spellingShingle Krysztowiak, P.
Sysło, M.M.
A tabu search approach to the jump number problem
Algebra and Discrete Mathematics
author_facet Krysztowiak, P.
Sysło, M.M.
author_sort Krysztowiak, P.
title A tabu search approach to the jump number problem
title_short 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_sort tabu search approach to the jump number problem
publisher Інститут прикладної математики і механіки НАН України
publishDate 2015
url https://nasplib.isofts.kiev.ua/handle/123456789/158002
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 назв. — англ.
series Algebra and Discrete Mathematics
work_keys_str_mv AT krysztowiakp atabusearchapproachtothejumpnumberproblem
AT sysłomm atabusearchapproachtothejumpnumberproblem
AT krysztowiakp tabusearchapproachtothejumpnumberproblem
AT sysłomm tabusearchapproachtothejumpnumberproblem
first_indexed 2025-11-25T22:45:11Z
last_indexed 2025-11-25T22:45:11Z
_version_ 1849804152956256256

Similar Items