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

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

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



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






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


Модел. и анализ информ. систем, 2014, том 21, номер 5, страницы 116–130 (Mi mais403)  

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

Характеристики сложности: кликовое число графа многогранника и число прямоугольного покрытия

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

Ярославский государственный университет им. П. Г. Демидова

Аннотация: В 1980-х гг. В. А. Бондаренко обнаружил, что кликовое число графа многогранника во многих случаях соответствует реальной сложности задачи оптимизации на вершинах этого многогранника. Для объяснения этого феномена была предложена теория алгоритмов прямого типа, утверждающая, что кликовое число графа многогранника является нижней оценкой сложности соответствующей задачи в так называемом классе алгоритмов прямого типа. Более того, утверждалось, что этот класс является достаточно широким, включающим в себя многие классические комбинаторные алгоритмы. В настоящей работе приводится несколько примеров, призванных обозначить границы применимости этой теории. В частности, описана довольно часто используемая на практике модификация алгоритмов, выводящая их из указанного класса (порядок трудоемкости при этом не меняется). Другой, значительно более близкой к реальности, комбинаторной характеристикой сложности является число прямоугольного покрытия матрицы инциденций фасет-вершин, введенное в рассмотрение М. Яннакакисом в 1988 г. Мы приводим пример многогранника с полиномиальным (относительно размерности многогранника) значением этой характеристики, задача оптимизации на вершинах которого NP-трудна.

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

Полный текст: PDF файл (494 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.85
Поступила в редакцию: 30.08.2014

Образец цитирования: А. Н. Максименко, “Характеристики сложности: кликовое число графа многогранника и число прямоугольного покрытия”, Модел. и анализ информ. систем, 21:5 (2014), 116–130

Цитирование в формате AMSBIB
\RBibitem{Mak14}
\by А.~Н.~Максименко
\paper Характеристики сложности: кликовое число графа многогранника и число прямоугольного покрытия
\jour Модел. и анализ информ. систем
\yr 2014
\vol 21
\issue 5
\pages 116--130
\mathnet{http://mi.mathnet.ru/mais403}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais403
  • http://mi.mathnet.ru/rus/mais/v21/i5/p116

    ОТПРАВИТЬ: 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. А. Н. Максименко, “Сложность задач комбинаторной оптимизации в терминах решёток граней ассоциированных многогранников”, Дискретн. анализ и исслед. опер., 23:3 (2016), 61–80  mathnet  crossref  mathscinet  elib; A. N. Maksimenko, “Complexity of combinatorial optimization problems in terms of face lattice of associated polytopes”, J. Appl. Industr. Math., 10:3 (2016), 370–379  crossref
    2. А. Н. Максименко, “Алгоритм ветвей и границ для задачи коммивояжера не является алгоритмом прямого типа”, Модел. и анализ информ. систем, 27:1 (2020), 72–85  mathnet  crossref
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:228
    Полный текст:88
    Литература:22
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020