Разработка моделей и эффективных алгоритмов для решения прикладных оптимизационных задач на дискретных структурах : отчет о научно-исследовательской работе (заключительный) / БГУ ; научный руководитель В. М. Котов

Abstract

Объектом исследования являются комбинаторно-геометрические конфигурации: графы, гиперграфы, расписания, разбиения, покрытия и упаковки. Цель работы – построение комбинаторных моделей и разработка эффективных алгоритмов для решения оптимизационных задач, связанных с важнейшими классами дискретных структур (графами, гиперграфами, расписаниями и другими объектами комбинаторной природы). Основные результаты исследований. Для задачи теории расписаний с сервером построено семейство градиентных алгоритмов и проведен анализ их качества. Доказано, что для фиксированных m ≥ 1 и k ≥ 3 задача распознавания класса графов пересечений ребер k-униформных гиперграфов кратности не выше m является NP-полной. Показано, что в предположении P не равно NP для любого фиксированного ε > 0 задача покрытия графа наименьшим числом клик и биклик не аппроксимируется с гарантированной оценкой n1 – ε в классе расщепляемых графов, где n – число вершин в расщепляемом графе. Установлены структурные характеризации 1-треугольных графов, связно-доминантно-треугольных графов и совершенных связно-окрестностных графов, из которых следуют полиномиальные алгоритмы распознавания этих классов графов. Выявлены новые структурные свойства покрытий и упаковок графа, которые применены при решении взвешенной задачи о независимой {K1, K2}-упаковке. Установлен ряд свойств A4-структуры (1, ∞)-простого графа и разработан полиномиальный алгоритм распознавания A4-структур (1, ∞)-простых графов. Установлены достаточные условия существования совершенного паросочетания в графах с ограниченным локальным строением.