Citeseer/Matroid and Knapsack Center Problems (2013) 10.1.1.768.8386 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/Matroid and Knapsack Center Problems (2013) 10.1.1.768.8386|<html> </html>}} {{enddiv}} Категория:CiteSeerArtic…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
{{citeseerlink|citeseer/Matroid and Knapsack Center Problems (2013) 10.1.1.768.8386|<html> | {{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>}} | </html>}} | ||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Текущая версия на 15:23, 23 ноября 2021
«
В классической задаче о k-центрах нам дается метрический граф, и задача состоит в том, чтобы выбрать k—вершин в качестве центров таким образом, чтобы максимальное расстояние от любой вершины до ближайшего центра было минимизировано.
В данной работе мы рассматриваем два важных обобщения k-центра — проблему матроидного центра и проблему центра ранца.
Обе проблемы мотивированы недавними приложениями сетей распространения контента. Наш вклад можно суммировать следующим образом:
* Рассматриваем проблему центра матроида, в которой центры должны образовывать независимое множество заданного матроида, показываем, что эта проблема NP-трудна даже на прямой.
* Представляем алгоритм 3-аппроксимации для этой задачи на общих метриках. Рассматриваем версию проблемы, в которой заданное число вершин может быть исключено как из решения.
** Представляем 7-аппроксимацию для версии с выбросами.
* Рассматриваем проблему (мульти)ранцевого центра, в которой центры должны удовлетворять одному (или нескольким) ограничению (ограничениям) ранца. Известно, что проблема центра ранца с одним ранцевым ограничением допускает 3-аппроксимацию. Однако, когда существует мы показываем, что эта задача вообще не аппроксимируема.
* Чтобы дополнить результат о трудности, мы представляем алгоритм, который за полиномиальное время дает 3-аппроксимируемое решение, такое, что одно ранцевое ограничение удовлетворяется, а остальные могут быть нарушены не более чем в 1 + ǫ раз.
** Получаем 3-аппроксимацию для версии с выбросом которая может нарушить ограничение ранца на 1 + ǫ.
…»