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

• Автор: Свириденко, Максим Иванович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Новосибирск
• Количество страниц: 130 с.

Оглавление
Введение
1 Простейшая задача размещения на максимум
Введение
1.1 Двухстороннее сведение ПЗР на максимум в сдвинутой форме к задаче MAX SAT*
1.2 Приближенный алгоритм для задачи MAX SAT*
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 Оценка относительной погрешности
Заключение
Список литературы
Список публикаций автора по теме диссертации

Введение
За последние десятилетия достигнуты значительные успехи в построении и развитии математического аппарата для обоснования решений в самых различных областях человеческой деятельности. Одним из таких интенсивно развивающихся направлений исследований является теория дискретных задач размещения, выделившаяся в самостоятельную научную дисциплину около тридцати лет назад.
Дискретные задачи размещения моделируют ситуации, в которых требуется в конечной области разместить конечное число объектов так, чтобы достичь наибольшего эффекта или получить наименьшие издержки. В реальной жизни в качестве размещаемых объектов могут выступать промышленные предприятия, различные средства обслуживания, складские системы, объекты оборонного назначения и многое другое.
В дискретных задачах размещения множество. допустимых решений конечно, поэтому заранее известно, что оптимальное решение существует. Более того существует универсальный способ отыскания такого решения посредством полного перебора всех допустимых решений. Однако такой алгоритм поиска применим только в тех исключи-

Наша задача оценить величину F1p/F*lp.
Так как (1/2
в т(т — 1) т 0 + 1 — тг = т т . (1.6)
- гп - 1
Пусть Тт = {/ £ [0,1] : 1т, целое число }. Для любого I 6 £т, пусть Ер обозначает общий вес выполненных дизъюнкций в С' где точно 1т переменных имеет значение "ЛОЖЬ”. Тогда, используя симметрию задачи, мы получаем:
F'lP = YIlF'ip
Imtlm — 1), в , i
< max —Ц- Ц- *)— h Im)
_ie[0,i]lv 2 2 m - 1 J
= max{ÈH + lm_Ë?++l}
ie[o,i] 2 2(m - 1)
m(lm — 1) , m
( так как > Im
v m — 1 - m
r //5 , , /»3 , ßl M
< max i ml — +1 — 4—;
“(eM 2 2 2(m-l)yi
r ,/3 , ßl2 ß 4,
< max {m(—f-1 h - r
/e[o,i] 2 2 2{m-l)ls
( так как ß > 1, максимум достигается при I. = 1/ß)
,ß2 I ' . ß
= ~2ß 2(ml)
Полагая ß = 1 + /2 и используя доказанные неравенства, получаем
Ffp < ß2 + l f /5
Flp ß(ß + 1) (m —!)(/? + !)