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

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

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



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






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


Дискретн. анализ и исслед. опер., 2016, том 23, номер 3, страницы 61–80 (Mi da852)  

Сложность задач комбинаторной оптимизации в терминах решёток граней ассоциированных многогранников

А. Н. Максименко

Ярославский гос. университет им. П. Г. Демидова, ул. Советская, 14, 150000 Ярославль, Россия

Аннотация: Основной мотивацией работы является следующий вопрос, связанный со свойствами многогранников, ассоциированных с задачами комбинаторной оптимизации. Можно ли, зная комбинаторные свойства многогранника, оценить сложность соответствующей оптимизационной задачи? В разное время в качестве таких ключевых характеристик сложности рассматривались число гиперграней многогранника, диаметр и кликовое число его графа, число прямоугольного покрытия матрицы инциденций вершин-гиперграней и некоторые другие. В настоящей работе приводится несколько примеров семейств многогранников, для которых значения упомянутых выше характеристик существенно отличаются от реальной вычислительной сложности соответствующих оптимизационных задач. В частности, приводятся примеры двух задач дискретной оптимизации, многогранники которых комбинаторно эквивалентны и длины двоичной записи координат вершин этих многогранников одинаковы. При этом первая задача разрешима за полиномиальное время, а вторая задача имеет экспоненциальную сложность. Ил. 1, библиогр. 22.

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

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


DOI: https://doi.org/10.17377/daio.2016.23.515

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2016, 10:3, 370–379

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

Тип публикации: Статья
УДК: 519.854
Статья поступила: 13.10.2015
Переработанный вариант: 19.04.2016

Образец цитирования: А. Н. Максименко, “Сложность задач комбинаторной оптимизации в терминах решёток граней ассоциированных многогранников”, Дискретн. анализ и исслед. опер., 23:3 (2016), 61–80; J. Appl. Industr. Math., 10:3 (2016), 370–379

Цитирование в формате AMSBIB
\RBibitem{Mak16}
\by А.~Н.~Максименко
\paper Сложность задач комбинаторной оптимизации в~терминах решёток граней ассоциированных многогранников
\jour Дискретн. анализ и исслед. опер.
\yr 2016
\vol 23
\issue 3
\pages 61--80
\mathnet{http://mi.mathnet.ru/da852}
\crossref{https://doi.org/10.17377/daio.2016.23.515}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3563716}
\elib{http://elibrary.ru/item.asp?id=26681830}
\transl
\jour J. Appl. Industr. Math.
\yr 2016
\vol 10
\issue 3
\pages 370--379
\crossref{https://doi.org/10.1134/S1990478916030078}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84983527686}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da852
  • http://mi.mathnet.ru/rus/da/v23/i3/p61

    ОТПРАВИТЬ: 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:176
    Полный текст:48
    Литература:20
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020