A tabu search approach to the jump number problem

• Published in: Algebra and Discrete Mathematics
• Date: 2015
• Main Authors: Krysztowiak, P., Sysło, M.M.
• Format: Article
• Language: English
• Published: Інститут прикладної математики і механіки НАН України 2015
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/158002
• 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 назв. — англ.

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