A tabu search approach to the jump number problem

• 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
• Journal Title: Algebra and Discrete Mathematics

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