Задача о размещении объектов: различия между версиями

В задаче UFL заданы множество <math>\mathcal{F}</math> из <math>n_f \;</math> ''объектов'' и множество <math>\mathcal{C} \;</math> из <math>n_c \;</math> ''клиентов'' (которые также могут называться ''городами'' или ''точками спроса''). Каждому объекту <math>i \in \mathcal{F}</math> назначена ''стоимость открытия объекта'' <math>f_i \;</math>. Кроме того, для каждого объекта <math>i \in \mathcal{F}</math> и клиента <math>j \in \mathcal{C}</math> задана ''стоимость соединения'' <math>c_{ij} \;</math>. Задача заключается в открытии подмножества объектов и соединении каждого клиента с открытым объектом таким образом, чтобы общая стоимость была минимальной. Заметим, что после определения множества открытых объектов оптимальным является соединение каждого клиента с открытым объектом, имеющее минимальную стоимость. Таким образом, задача заключается в нахождении множества <math>S \subseteq \mathcal{F}</math>, минимизирующего значение <math>\sum_{i \in S} f_i + \sum_{j \in C} min_{i \in S} \{ c_{ij} \}</math>. Это определение и определения других вариантов задачи о размещении объектов далее будут предполагать единичный спрос у каждого клиента. Обобщение определений до случая с заданным спросом у каждого отдельного клиента является тривиальным. Задачу UFL можно сформулировать в виде следующей целочисленной программы, предложенной Балински [7]. Пусть <math>y_i, i \in \mathcal{F},</math> равно 1 в случае, если объект открыт, и 0 в противном случае. <math>Пусть x_{ij}, i \in \mathcal{F}, j \in \mathcal{C}</math>, – доля клиента j, назначенная объекту i.

Хохбаум [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].