Алгоритмы с оценками для дискретных задач размещения Свириденко Максим Иванович

Короткий опис

Свириденко, Максим Иванович.
Алгоритмы с оценками для дискретных задач размещения : диссертация ... кандидата физико-математических наук : 01.01.09. - Новосибирск, 1998. - 130 с.
Оглавление диссертациикандидат физико-математических наук Свириденко, Максим Иванович
Введение
1 Простейшая задача размещения на максимум
Введение
1.1 Двухстороннее сведение ПЗР на максимум в сдвинутой форме к задаче MAX SAT*.
1.2 Приближенный алгоритм для задачи MAX SAT*
1.3 Сложность аппроксимации.
1.4 Разрыв двойственности
2 Задача о р-медиане на максимум и ее обобщения
Введение.
2.1 Свойства функции f(S).
2.2 Оценки точности жадных алгоритмов.
2.3 Динамическая задача о р-медиане на максимум.
2.4 Эквивалентная формулировка динамической задачи о р-медиане на максимум.
2.5 Приближенный алгоритм и его анализ.
2.6 Дерандомизация алгоритма.
3 Новая техника округления для задач с ограничением мощность
Введение.
3.1 Задача о максимальном покрытии р множествами
3.2 Задача о максимальном разрезе с ограничением на мощность
3.3 Задача о максимальном к-разрезе с ограничениями на мощность.
3.4 Задача о максимальном покрытии с ранцевым ограничением
4 Задача выполнимости на максимум с ограничением на мощность
Введение.
4.1 Линейная релаксация и приближенный алгоритм
4.2 Анализ алгоритма.
4.2.1 Технические леммы.
4.2.2 Оценка математического ожидания.
4.3 Дерандомизация.
5 Квадратичная задача о назначениях
Введение
5.1 Алгоритм и его анализ.
6 Задача о р-центре
Введение.
6.1 Описание и анализ алгоритма.
6.2 Оценка относительной погрешности.