|
СЕМИНАРЫ |
|
Анализ сложности многогранников задач комбинаторной оптимизации А. Н. Максименко Ярославский государственный университет им. П. Г. Демидова |
|||
Аннотация: Многие современные эффективные алгоритмы решения задач комбинаторной оптимизации основаны на рассмотрении так называемых ассоциированных многогранников. Особое внимание в этом направлении уделяется изучению свойств выпуклых многогранников (а точнее — семейств многогранников), ассоциированных с NP-трудными задачами (задача коммивояжера, задача о рюкзаке, задача выполнимости булевых формул, задача о раскраске графа и т.п.). Накопленные к настоящему времени факты говорят о том, что упомянутые многогранники обладают рядом схожих свойств, существенно отличающихся от свойств многогранников, ассоциированных с известными полиномиально–разрешимыми задачами (задача о назначениях, задача о минимальном остовном дереве, задача о кратчайшем пути и др.). Наиболее интересными примерами таких свойств являются: экспоненциальное кликовое число графа многогранника и экспоненциальная сложность прямоугольного покрытия матрицы инциденций вершин–гиперграней многогранника. По аналогии с классической полиномиальной сводимостью С. Кука, Р. Карпа и Л. А. Левина, автор доклада вводит понятие аффинной сводимости семейств многогранников, основанное на следующем естественном способе сравнения многогранников. Если многогранник С другой стороны, будут представлены несколько специальным образом сконструированных примеров задач комбинаторной оптимизации, для многогранников которых указанные выше свойства (кликовое число графа и сложность прямоугольного покрытия матрицы инциденций вершин–гиперграней) существенно отличаются от реальной вычислительной сложности задачи. Более того, будет доказана несостоятельность попыток оценки сложности задачи с помощью комбинаторных характеристик соответствующего многогранника. |