A tabu search approach to the jump number problem

A tabu search approach to the jump number problem

We consider algorithmics for the jump number problem, which isto generate a linear extension of a given poset, minimizing the numberof incomparable adjacent pairs. Since this problem is NP-hardon interval orders and open on two-dimensional posets,approximation algorithms orfast exact algorithms are...

Full description

Saved in:
Bibliographic Details
Date:2015
Main Authors: Krysztowiak, Przemysław, Sysło, Maciej M.
Format: Article
Language:English
Published: Lugansk National Taras Shevchenko University 2015
Subjects:
graph theory
poset
jump number
combinatorial optimization
tabu search
90C27
90C59
Online Access:https://admjournal.luguniv.edu.ua/index.php/adm/article/view/101
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Algebra and Discrete Mathematics

Institution

Algebra and Discrete Mathematics
id oai:ojs.admjournal.luguniv.edu.ua:article-101
record_format ojs
spelling oai:ojs.admjournal.luguniv.edu.ua:article-1012015-11-10T19:25:54Z A tabu search approach to the jump number problem Krysztowiak, Przemysław Sysło, Maciej M. graph theory, poset, jump number, combinatorial optimization, tabu search 90C27, 90C59 We consider algorithmics for the jump number problem, which isto generate a linear extension of a given poset, minimizing the numberof incomparable adjacent pairs. Since this problem is NP-hardon interval orders and open on two-dimensional posets,approximation algorithms orfast exact algorithms are in demand.In this paper, succeeding from the work of the second named author onsemi-strongly greedylinear extensions, we develop a metaheuristic algorithm to approximatethe jump number with the tabu search paradigm. To benchmarkthe proposed procedure, we infer from the previous work of Mitas[Order 8 (1991), 115--132]a new fast exact algorithm for the case ofinterval orders, and from the results of Ceroi[Order 20 (2003), 1--11]a lower boundfor the jump number of two-dimensional posets.Moreover, by other techniques we provean approximation ratio of \(n / \log\log n\) for 2D orders. Lugansk National Taras Shevchenko University 2015-11-09 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/101 Algebra and Discrete Mathematics; Vol 20, No 1 (2015): A special issue 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/101/31 Copyright (c) 2015 Algebra and Discrete Mathematics
institution Algebra and Discrete Mathematics
baseUrl_str
datestamp_date 2015-11-10T19:25:54Z
collection OJS
language English
topic graph theory
poset
jump number
combinatorial optimization
tabu search
90C27
90C59
spellingShingle graph theory
poset
jump number
combinatorial optimization
tabu search
90C27
90C59
Krysztowiak, Przemysław
Sysło, Maciej M.
A tabu search approach to the jump number problem
topic_facet graph theory
poset
jump number
combinatorial optimization
tabu search
90C27
90C59
format Article
author Krysztowiak, Przemysław
Sysło, Maciej M.
author_facet Krysztowiak, Przemysław
Sysło, Maciej M.
author_sort Krysztowiak, Przemysław
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
description We consider algorithmics for the jump number problem, which isto generate a linear extension of a given poset, minimizing the numberof incomparable adjacent pairs. Since this problem is NP-hardon interval orders and open on two-dimensional posets,approximation algorithms orfast exact algorithms are in demand.In this paper, succeeding from the work of the second named author onsemi-strongly greedylinear extensions, we develop a metaheuristic algorithm to approximatethe jump number with the tabu search paradigm. To benchmarkthe proposed procedure, we infer from the previous work of Mitas[Order 8 (1991), 115--132]a new fast exact algorithm for the case ofinterval orders, and from the results of Ceroi[Order 20 (2003), 1--11]a lower boundfor the jump number of two-dimensional posets.Moreover, by other techniques we provean approximation ratio of \(n / \log\log n\) for 2D orders.
publisher Lugansk National Taras Shevchenko University
publishDate 2015
url https://admjournal.luguniv.edu.ua/index.php/adm/article/view/101
work_keys_str_mv AT krysztowiakprzemysław atabusearchapproachtothejumpnumberproblem
AT sysłomaciejm atabusearchapproachtothejumpnumberproblem
AT krysztowiakprzemysław tabusearchapproachtothejumpnumberproblem
AT sysłomaciejm tabusearchapproachtothejumpnumberproblem
first_indexed 2025-07-17T10:29:51Z
last_indexed 2025-07-17T10:29:51Z
_version_ 1837889688600313856

Similar Items