В капаситированных Facility Местоположение задачи (CFLP) , нам дано множество клиентов и набор потенциальных объектов . У каждого клиента есть спрос который должен обслуживаться одним или несколькими открытыми средствами. Каждый объект имеет стоимость открытия и имеет емкость , что является максимальным требованием , что объект могу служить. Стоимость обслуживания одной единицы спроса клиента в учреждении составляет, Мы хотим открыть подмножество объектов и назначить спрос клиентов на открытие объектов таким образом, чтобы были удовлетворены требования всех клиентов, не нарушалось ограничение пропускной способности и сводилась к минимуму общая стоимость открытия объектов и обслуживания клиентов. Стоимость услуг неотрицательна, симметрична и удовлетворяет неравенству треугольника.
Арора в [ 1 , стр. 21] утверждает, что «Арора, Рагхаван и Рао [ 2 ] дают PTAS для геометрического случая. Они распространяют алгоритм на случай с емкостью, но окончательное решение может незначительно нарушать ограничения по емкости». Что он подразумевает под «небольшим количеством»? Я предполагаю, что это означает, что они дают PTAS, который нарушает ограничения емкости в пределах фактора для произвольного . Это правильно?
Когда я посмотрел в [ 2 ], единственным связанным результатом, который я нашел, был алгоритм времени для нахождения -приближенного решения для капаситированные -медиана когда мы имеем единые возможности. Арора ссылается на приведенный выше результат в [ 1 ]?
[ 1 ] С. Арора. Аппроксимационные схемы для задач NP-сложной геометрической оптимизации: обзор. В математике Программирование, Сер. B, vol. 97, стр. 43-69, 2003.
[ 2 ] С. Арора, П. Рагхаван и С. Рао. Аппроксимационные схемы для евклидовых k-медиан и связанные с ними проблемы. В учеб. 30-й симпозиум ACM по теории вычислений, стр. 106–113, 1998.
источник