Citeseer/Matroid and Knapsack Center Problems (2013) 10.1.1.768.8386
Материал из DISCOPAL
«
В классической задаче о k-центрах нам дается метрический граф, и задача состоит в том, чтобы выбрать k—вершин в качестве центров таким образом, чтобы максимальное расстояние от любой вершины до ближайшего центра было минимизировано.
В данной работе мы рассматриваем два важных обобщения k-центра — проблему матроидного центра и проблему центра ранца.
Обе проблемы мотивированы недавними приложениями сетей распространения контента. Наш вклад можно суммировать следующим образом:
* Рассматриваем проблему центра матроида, в которой центры должны образовывать независимое множество заданного матроида, показываем, что эта проблема NP-трудна даже на прямой.
* Представляем алгоритм 3-аппроксимации для этой задачи на общих метриках. Рассматриваем версию проблемы, в которой заданное число вершин может быть исключено как из решения.
** Представляем 7-аппроксимацию для версии с выбросами.
* Рассматриваем проблему (мульти)ранцевого центра, в которой центры должны удовлетворять одному (или нескольким) ограничению (ограничениям) ранца. Известно, что проблема центра ранца с одним ранцевым ограничением допускает 3-аппроксимацию. Однако, когда существует мы показываем, что эта задача вообще не аппроксимируема.
* Чтобы дополнить результат о трудности, мы представляем алгоритм, который за полиномиальное время дает 3-аппроксимируемое решение, такое, что одно ранцевое ограничение удовлетворяется, а остальные могут быть нарушены не более чем в 1 + ǫ раз.
** Получаем 3-аппроксимацию для версии с выбросом которая может нарушить ограничение ранца на 1 + ǫ.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.