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

Abstract

Объектом исследования являются задачи теории расписаний и теории графов. Целью работы является исследование алгоритмической сложности и сложности аппроксимации теоретико-графовых задач, связанных с параметрами независимости и доминирования; построение эффективных алгоритмов для задач теории расписаний; исследование гамильтоновых свойств графов. Основные результаты исследований. Предложены модели, разработаны методы и приближенные алгоритмы для онлайн и семи онлайн версий задач теории расписаний с критерием минимизации общего времени завершения обслуживания всех работ. Получены новые оценки погрешности в задачах теории расписаний на основе детального изучения структуры множества оптимальных решений и использования динамических нижних оценок. Найдена характеризация класса хорошо согласованных графов в терминах минимальных запрещенных косогласованных подграфов. Установлена вычислительная сложность и сложность аппроксимации в конаследственных и окрестностно наследственных классах графов ряда теоретико-графовых параметров, родственных классическим числам независимости и доминирования. В предположении P  NP для задач нахождения наименьшего доминирующего множества, наименьшего окрестностного множества, наименьшего максимального ирридантного множества доказано, что не существует полиномиального (k ln n)-приближенного алгоритма в классе расщепляемых доминантно-треугольных графов порядка n, где k >0 – некоторая фиксированная константа. Установлена вычислительная сложность задачи о гамильтоновом цикле в классе локально связных графов с дополнительными ограничениями на степени вершин.