АННОТАЦИЯ 2
Введение 2
1 Постановка задачи 3
1.1 Задача о размещении объектов 3
1.2 Пропорциональный механизм 4
2 Предварительные сведения 5
3 Основной результат 6
4 Случай кластерных пространств с равными ai 9
Список литературы 10
Задача размещения объектов в простейшем случае была поставлена ещё Пьером Ферма в первой половине XVII века. В формулировке Ферма она состаяла в том, чтобы для трёх данных точек A, B и C найти такую точку X, чтобы сумма расстояний AX + BX + CX была минимальной. Изящный ответ на этот вопрос в 1645 году дал Эванджелиста Торричелли.
В более общем случае задача о размещении объектов (также известная как задача о нахождении k-центра ) состоит в том, чтобы для n точек '1,'2,... ,'п — координат игроков в метрическом пространстве Q найти к точек f 1, f2, • • • , fk — координат объектов таких, что сумма
п к
^Ijnn d('i,fj) i= 1 3
была минимальной. Здесь через d('i, fj) обозначено расстояние между точками ' и fj в Q. Более подробная формулировка приведена в подразделе 1.1.
Как в 1981 году показали в работе [3] Фаулер, Патерсон и Танимото, в общем случае задача о размещении NP-трудна. Более того, как показано в статье [6] также NP-трудно получить алгоритм аппроксимирующий оптимум с константой 1,463 в предположении того, что P = NP.
Лучший на данный момент полиномиальный алгоритм, описанный Ли в 2011 году в статье [7] аппроксимирует оптимум с константой 1,488.
В этой работе Пропорциональный механизм работает естественным образом, принимая решения о строительстве объектов в к последовательных раундах. Каждый раз, мы выбираем следующее место в локации одного из игроков, давая каждому игроку шанс быть выбранным пропорционально расстоянию игрока от набора построенных на данный момент объектов.
Простота описания, полиномиальное время работы и возможность остановить работу алгоритма в любой момент делают этот механизм очень эффективным на практике.
Простые случаи (к = 1 и к = 2) были рассмотрены в работе [4]. В статьях [1] и [5] был рассмотрен общий случай работы пропорционального механизма и доказана оценка аппроксимации 4к.
Также в работе [5] описан частный случай, для которого пропорциональный механизм не может аппроксимировать оптимум с константой лучшей, чем O(logк).
В этой работе мы докажем (см. теорему 3.1), что Пропорциональный механизм аппроксимирует оптимум с константой O(log к).
