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

В k-уровневой задаче о размещении объектов заданы следующие начальные данные: множество клиентов C, k непересекающихся множеств <math>\mathcal{F}_1, ..., \mathcal{F}_k</math> объектов, стоимость открытия каждого объекта и стоимость соединения клиентов и объектов. Задача заключается в соединении каждого клиента j по пути, состоящему из открытых объектов <math>i_1, ... , i_k \;</math>, где <math>i_{\ell} = \mathcal{F}_{\ell}</math>. Стоимость соединения для этого объекта имеет вид <math>c_{ji_1} + c_{i_1 i_2} + ... + c_{i_{k - 1}i_k} \;</math>. Задача заключается в минимизации суммы стоимостей соединений и стоимостей открытия объектов.

Все вышеупомянутые задачи были рассмотрены в работе Шмойса, Тардош и Аардал [15] за исключением задач max-UFL, о k-центрах и k-медианах. Вариант max-UFL был добавлен по историческим причинам, а задачи о k-центрах и k-медианах включены в силу их богатой истории и близкого родства с задачей UFL. Результаты для задачи о размещении объектов с жесткими ограничениями на пропускную способность упомянуты, поскольку, по крайней мере с точки зрения приложения, эта модель более реалистична по сравнению с версией с мягкими ограничениями, рассмотренной в [51]. Для k-уровневой задачи о размещении объектов Шмойс и др. рассматривали случай k = 2. Здесь рассматривается задача для k общего вида.