4551
правка
Задача о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача о размещении объектов (посмотреть исходный код)
Версия от 12:09, 24 апреля 2018
, 24 апреля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 27: | Строка 27: | ||
Хохбаум [25] разработала алгоритм O(log n)-аппроксимации для задачи UFL. Путем прямой редукции задачи о покрытии множества можно показать, что результат не может быть улучшен иначе как в случае NP | Хохбаум [25] разработала алгоритм O(log n)-аппроксимации для задачи UFL. Путем прямой редукции задачи о покрытии множества можно показать, что результат не может быть улучшен иначе как в случае <math>NP \subseteq DTIME[n^{O(log \; log \; n)}]</math> в силу результата, полученного Фейге [17]. Однако, если стоимость соединения ограничена в силу некоторых свойств расстояния в метрическом пространстве, а именно <math>c_{ij} = c_{ji} \ge 0 \;</math> для всех <math>i \in \mathcal{F}, j \in \mathcal{C}</math> (неотрицательность и симметричность) и <math>c_{ij} + c_{ji'} + c_{i'j'} \ge c_{i j'} \;</math> для всех <math>i, i' \in \mathcal{F}, j, j' \in \mathcal{C}</math> (неравенство треугольника), то можно получить гарантии константной аппроксимации. Во всех упомянутых выше результатах, за исключением задачи максимизации, предполагается, что стоимости удовлетворяют этим ограничениям. Для случая евклидовых расстояний между объектами и клиентами были получены схемы аппроксимации для некоторых задач о размещении объектов [5]. | ||
'''Варианты и родственные задачи''' | '''Варианты и родственные задачи''' | ||