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

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

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



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






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


Модел. и анализ информ. систем, 2016, том 23, номер 1, страницы 23–40 (Mi mais481)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

A special role of Boolean quadratic polytopes among other combinatorial polytopes

[Особое место булевых квадратичных многогранников среди других комбинаторных многогранников]

A. N. Maksimenko

P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia

Аннотация: Рассматриваются несколько семейств комбинаторных многогранников, ассоциированных со следующими NP-полными задачами: максимальный разрез, булево квадратичное программирование, квадратичная задача линейного упорядочения, квадратичные назначения, разбиение и упаковка множества, независимое множество, $3$-назначения. Для сравнения двух семейств многогранников используется следующий способ. Будем говорить, что семейство $P$ аффинно сводится к семейству $Q$, если для каждого многогранника $p\in P$ найдется $q\in Q$ такой, что $p$ аффинно эквивалентен $q$ или некоторой грани $q$, где $\dim q = O((\dim p)^k)$ для некоторой константы $k$. При таком способе сравнения упомянутые выше семейства разбиваются на два класса эквивалентности. Показано также, что эти два класса проще (в указанном смысле), чем семейства многогранников следующих задач: покрытие множества, коммивояжер, $0/1$ рюкзак, $3$-выполнимость, кубический подграф, частичное упорядочение. В частности, булевы квадратичные многогранники оказываются гранями многогранников каждого из упомянутых семейств.
Статья публикуется в авторской редакции.

Ключевые слова: NP-трудные задачи, аффинная сводимость, грани многогранников.

Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации 477
Работа выполнена при поддержке проекта № 477 базовой части гос. задания на НИР ЯрГУ.


DOI: https://doi.org/10.18255/1818-1015-2016-1-23-40

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

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.854.33
Поступила в редакцию: 15.11.2015
Язык публикации: английский

Образец цитирования: A. N. Maksimenko, “A special role of Boolean quadratic polytopes among other combinatorial polytopes”, Модел. и анализ информ. систем, 23:1 (2016), 23–40

Цитирование в формате AMSBIB
\RBibitem{Mak16}
\by A.~N.~Maksimenko
\paper A special role of Boolean quadratic polytopes among other combinatorial polytopes
\jour Модел. и анализ информ. систем
\yr 2016
\vol 23
\issue 1
\pages 23--40
\mathnet{http://mi.mathnet.ru/mais481}
\crossref{https://doi.org/10.18255/1818-1015-2016-1-23-40}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3502273}
\elib{http://elibrary.ru/item.asp?id=25475539}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais481
  • http://mi.mathnet.ru/rus/mais/v23/i1/p23

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. А. Н. Максименко, “Об одном семействе 0/1-многогранников с NP-полным критерием несмежности вершин”, Дискрет. матем., 29:2 (2017), 29–39  mathnet  crossref  elib; A. N. Maksimenko, “On a family of 0/1-polytopes with an NP-complete criterion for vertex nonadjacency relation”, Discrete Math. Appl., 29:1 (2019), 7–14  crossref  isi
    2. А. Н. Максименко, “Булев квадратичный многогранник является гранью многогранника линейных порядков”, Сиб. электрон. матем. изв., 14 (2017), 640–646  mathnet  crossref
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:92
    Полный текст:37
    Литература:43

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019