Оглавление
Введение
1 Простейшая задача размещения на максимум
Введение
1.1 Двухстороннее сведение ПЗР на максимум в сдвинутой форме к задаче X .
1.2 Приближенный алгоритм для задачи X
1.3 Сложность аппроксимации.
1.4 Разрыв двойственности
2 Задача о рмедиане на максимум и ее обобщения
Введение
2.1 Свойства функции .
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 Оценка относительной погрешности.
Заключение
Список литературы
- Київ+380960830922