Citeseer/Matroid and Knapsack Center Problems (2013) 10.1.1.768.8386

Материал из DISCOPAL
Версия от 15:23, 23 ноября 2021; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

« В классической задаче о k-центрах нам дается метрический граф, и задача состоит в том, чтобы выбрать k—вершин в качестве центров таким образом, чтобы максимальное расстояние от любой вершины до ближайшего центра было минимизировано. В данной работе мы рассматриваем два важных обобщения k-центра — проблему матроидного центра и проблему центра ранца. Обе проблемы мотивированы недавними приложениями сетей распространения контента. Наш вклад можно суммировать следующим образом: * Рассматриваем проблему центра матроида, в которой центры должны образовывать независимое множество заданного матроида, показываем, что эта проблема NP-трудна даже на прямой. * Представляем алгоритм 3-аппроксимации для этой задачи на общих метриках. Рассматриваем версию проблемы, в которой заданное число вершин может быть исключено как из решения. ** Представляем 7-аппроксимацию для версии с выбросами. * Рассматриваем проблему (мульти)ранцевого центра, в которой центры должны удовлетворять одному (или нескольким) ограничению (ограничениям) ранца. Известно, что проблема центра ранца с одним ранцевым ограничением допускает 3-аппроксимацию. Однако, когда существует мы показываем, что эта задача вообще не аппроксимируема. * Чтобы дополнить результат о трудности, мы представляем алгоритм, который за полиномиальное время дает 3-аппроксимируемое решение, такое, что одно ранцевое ограничение удовлетворяется, а остальные могут быть нарушены не более чем в 1 + ǫ раз. ** Получаем 3-аппроксимацию для версии с выбросом которая может нарушить ограничение ранца на 1 + ǫ. …»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.