Проблема размещения евклидовых емкостей

9

В капаситированных Facility Местоположение задачи (CFLP) , нам дано множество клиентов и набор потенциальных объектов . У каждого клиента есть спрос который должен обслуживаться одним или несколькими открытыми средствами. Каждый объект имеет стоимость открытия и имеет емкость , что является максимальным требованием , что объект могу служить. Стоимость обслуживания одной единицы спроса клиента в учреждении составляетCFjCdjiFfiuiijicij, Мы хотим открыть подмножество объектов и назначить спрос клиентов на открытие объектов таким образом, чтобы были удовлетворены требования всех клиентов, не нарушалось ограничение пропускной способности и сводилась к минимуму общая стоимость открытия объектов и обслуживания клиентов. Стоимость услуг неотрицательна, симметрична и удовлетворяет неравенству треугольника.

Арора в [ 1 , стр. 21] утверждает, что «Арора, Рагхаван и Рао [ 2 ] дают PTAS для геометрического случая. Они распространяют алгоритм на случай с емкостью, но окончательное решение может незначительно нарушать ограничения по емкости». Что он подразумевает под «небольшим количеством»? Я предполагаю, что это означает, что они дают PTAS, который нарушает ограничения емкости в пределах фактора для произвольного . Это правильно?(1+ϵ)ϵ>0

Когда я посмотрел в [ 2 ], единственным связанным результатом, который я нашел, был алгоритм времени для нахождения -приближенного решения для капаситированные -медиана когда мы имеем единые возможности. Арора ссылается на приведенный выше результат в [ 1 ]?nO(log2(n/ϵ))(1+ϵ)k

[ 1 ] С. Арора. Аппроксимационные схемы для задач NP-сложной геометрической оптимизации: обзор. В математике Программирование, Сер. B, vol. 97, стр. 43-69, 2003.

[ 2 ] С. Арора, П. Рагхаван и С. Рао. Аппроксимационные схемы для евклидовых k-медиан и связанные с ними проблемы. В учеб. 30-й симпозиум ACM по теории вычислений, стр. 106–113, 1998.

Бабак Бехсаз
источник

Ответы:

3

Если я правильно запомнил, вам нужно приблизить количество клиентов, подключенных к каждому шлюзу. В противном случае вы бы сразу получили что-то вроде , где - количество гейтов в подзадаче. Путем аппроксимации этого числа до значения течение всего динамического программирования можно получить ошибку в конце. Это дало бы время выполнения, аналогичное тому, которое вы указали выше.O(nO(g))g(1+ε/logn)(1+ε)

Сариэль Хар-Пелед
источник
Если я правильно понял, вы имеете в виду, что их алгоритм распространяется на QPTAS с нарушением мощностей для задачи с равномерным размещением емкостного объекта. Интересно, есть ли PTAS с нарушением для этой проблемы. (1+ϵ)(1+ϵ)
Бабак Бехсаз
Это действительно интересный вопрос. В то время казалось, что для этого можно продлить бумагу Коллиопулоса и Рао.
Сариэль Хар-Пелед
Некоторое время я думал так же, но когда несколько месяцев назад я перечитал доказательство теоремы 4 [Kolliopoulos-Rao-ESA'99], я обнаружил, что эту теорему нельзя применять в качестве черного ящика. Причина в том, что в доказательстве они предполагают, что можно назначить клиента для любого открытого объекта, в то время как в емкостном корпусе вы можете нарушить пропускную способность этой модификацией. Там может быть простой способ обойти это, я не особо задумывался об этом.
Бабак Бехсаз