Анализ комбинаторно-геометрических свойств задач и алгоритмов дискретной оптимизации
| Номер гранта: | 03-01-00822 |
| Область научного знания: | математика, механика, информатика |
| Тип конкурса: | («а» (до 2016))(«а») инициативные научные проекты |
| Год выполнения: | 2003г. |
| Руководитель: | Бондаренко В. А. |
| Статус заявки: | поддержана |
Аннотация к заявке:
Предполагается продолжить изучение комбинаторно - геометрических характеристик сложности дискретных задач с целью выяснения причин труднорешаемости и определения подходов для конструирования алгоритмов с приемлемой временной трудоемкостью. Основные направления исследований: - разработка новых комбинаторных конструкций, позволяющих эффективное использование современных методов линейного программирования; - геометрические и алгоритмические вопросы многокритериальной оптимизации: анализ сложности задач Парето-оптимизации и разработка эффективных алгоритмов.Аннотация к отчету:
Исследовались многокритериальные задачи оптимизации на конечном множестве с равноценными критериями. Для следующих двухкритериальных задач была доказана их NP-полнота: 1) остов ограниченного диаметра, с диаметром не превосходящим трех; 2) задача о независимом множестве для графа, не имеющего вершин степени выше 2; 3) задача о коалиции. Для двухкритериальной задачи остов ограниченного диаметра, с диаметром не превосходящим трех, построен псевдополиномиальный алгоритм. В результате проведенных в 2003 году исследований было установлено, что существующие алгоритмы сводимости задач комбинаторной оптимизации обладают, как правило, хорошим свойством: аффинно отображают пространство исходных данных одной задачи в некоторое аффинное подмножество исходных данных для другой задачи. Как следствие, была установлена следующая взаимосвязь между сводимостью задач комбинаторной оптимизации и свойствами их многогранников: Если задача X аффинно сводится к задаче Y, то многогранник задачи X является гранью многогранника задачи Y. Из этого утверждения следует, в частности, что граф многогранника задачи X является подграфом полиэдрального графа задачи Y. Для проверки изложенных умозаключений для некоторых наиболее известных задач комбинаторной оптимизации были сконструированы следующие алгоритмы: 1) алгоритм сведения задачи КЛИКА к задаче КОММИВОЯЖЕР; 2) алгоритм сведения задачи 3-СОЧЕТАНИЕ к задаче РЮКЗАК; 3) алгоритм сведения задачи КОММИВОЯЖЕР к задаче ДЛИННЕЙШИЙ ПУТЬ. В качестве шаблона были взяты известные алгоритмы сведения соответствующих задач распознавания. Оказалось, что все они обладают свойством аффинности. Кроме того, на предмет аффинности было проверено еще несколько алгоритмов сведения различных вариаций указанных задач. Все эти проверки также дали положительный результат. Как следствие этого, было показано, что многогранник задачи КЛИКА является гранью для многогранников задач КОММИВОЯЖЕР и ДЛИННЕЙШИЙ (КРАТЧАЙШИЙ) ПУТЬ. Кроме того, оказалось, что многогранник задачи 3-СОЧЕТАНИЕ является гранью многогранника задачи РЮКЗАК. Из этого следует, в частности, что плотность полиэдрального графа задачи РЮКЗАК экспоненциальна. Здесь необходимо отметить, что исследования свойств многогранника задачи РЮКЗАК представляют особый интерес. Дело в том, что множество его вершин представляет собой множество вершин единичного n-мерного куба, расположенное с одной стороны от рассекающей куб произвольной гиперплоскости.Аннотации к заявке и отчету приведены в авторской редакции. По состоянию на 27.08.2025
Поделиться:
