RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Algebra Discrete Math.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Algebra Discrete Math., 2015, том 20, выпуск 1, страницы 89–114 (Mi adm533)  

RESEARCH ARTICLE

A tabu search approach to the jump number problem

Przemysław Krysztowiak, Maciej M. Sysło

Faculty of Mathematics and Computer Science, Nikolaus Copernicus University, Torun

Аннотация: We consider algorithmics for the jump number problem, which is to generate a linear extension of a given poset, minimizing the number of incomparable adjacent pairs. Since this problem is NP-hard on interval orders and open on two-dimensional posets, approximation algorithms or fast exact algorithms are in demand.
In this paper, succeeding from the work of the second named author on semi-strongly greedy linear extensions, we develop a metaheuristic algorithm to approximate the jump number with the tabu search paradigm. To benchmark the proposed procedure, we infer from the previous work of Mitas [Order 8 (1991), 115–132] a new fast exact algorithm for the case of interval orders, and from the results of Ceroi [Order 20 (2003), 1–11] a lower bound for the jump number of two-dimensional posets. Moreover, by other techniques we prove an approximation ratio of $n / \log\log n$ for 2D orders.

Ключевые слова: graph theory, poset, jump number, combinatorial optimization, tabu search.

Полный текст: PDF файл (542 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
Тип публикации: Статья
MSC: 90C27, 90C59
Поступила в редакцию: 29.11.2013
Исправленный вариант: 29.11.2013
Язык публикации: английский

Образец цитирования: Przemysław Krysztowiak, Maciej M. Sysło, “A tabu search approach to the jump number problem”, Algebra Discrete Math., 20:1 (2015), 89–114

Цитирование в формате AMSBIB
\RBibitem{KrySys15}
\by Przemys\l aw~Krysztowiak, Maciej~M.~Sys\l o
\paper A tabu search approach to the jump number problem
\jour Algebra Discrete Math.
\yr 2015
\vol 20
\issue 1
\pages 89--114
\mathnet{http://mi.mathnet.ru/adm533}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3431953}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000378728700008}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/adm533
  • http://mi.mathnet.ru/rus/adm/v20/i1/p89

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Algebra and Discrete Mathematics
    Просмотров:
    Эта страница:89
    Полный текст:52
    Литература:24
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020