Просмотр исходного текста страницы Citeseer/Matroid and Knapsack Center Problems (2013) 10.1.1.768.8386

{{checked|}}
{{citeseerlink|citeseer/Matroid and Knapsack Center Problems (2013) 10.1.1.768.8386|<html>
В классической задаче о k-центрах нам дается метрический граф, и задача состоит в том, чтобы выбрать k—вершин в качестве центров таким образом, чтобы максимальное расстояние от любой вершины до ближайшего центра было минимизировано. 

В данной работе мы рассматриваем два важных обобщения k-центра — проблему матроидного центра и проблему центра ранца.

Обе проблемы мотивированы недавними приложениями сетей распространения контента. Наш вклад можно суммировать следующим образом:

* Рассматриваем проблему центра матроида, в которой центры должны образовывать независимое множество заданного матроида, показываем, что эта проблема NP-трудна даже на прямой. 
* Представляем алгоритм 3-аппроксимации для этой задачи на общих метриках. Рассматриваем версию проблемы, в которой заданное число вершин может быть исключено как из решения. 
** Представляем 7-аппроксимацию для версии с выбросами.
* Рассматриваем проблему (мульти)ранцевого центра, в которой центры должны удовлетворять одному (или нескольким) ограничению (ограничениям) ранца. Известно, что проблема центра ранца с одним ранцевым ограничением допускает 3-аппроксимацию. Однако, когда существует мы показываем, что эта задача вообще не аппроксимируема. 
* Чтобы дополнить результат о трудности, мы представляем алгоритм, который за полиномиальное время дает 3-аппроксимируемое решение, такое, что одно ранцевое ограничение удовлетворяется, а остальные могут быть нарушены не более чем в 1 + ǫ раз. 
** Получаем 3-аппроксимацию для версии с выбросом которая может нарушить ограничение ранца на 1 + ǫ.
</html>}}
{{enddiv}}

[[Категория:CiteSeerArticles]]