Найти множество S, которая максимизирует минимальное расстояние между точками S союза A

Question

Я хотел бы найти множество S из заданной мощности к максимизируя минимальное расстояние между каждыми точками и заданное множество . Существует ли простой алгоритм для нахождения решения этой задачи max-min?

Given a universe X ⊆ R^d and A ⊆ X,
find the argmax_{S⊆X, |S|=k} min_{s⊆S, s'≠s ⊆ S∪A} distance(s,s')

Спасибо!

Answer 1

Возможно, это NP-жесткий. Жесткий выбор точки, наиболее удаленной от предыдущих выборов, - это 2-приближение. Может быть сложная схема аппроксимации для низких d на основе схемы для евклидова TSP Аророй и Митчеллом. Для d = 10 забудьте об этом.

Answer 2

2 лучших результатов поиска sphere packing np complete ссылки на бумагу 1981 года, подтверждающие, что оптимальная упаковка и покрытие в 2d полностью завершены. У меня нет доступа к исследовательской библиотеке, поэтому я не могу прочитать статью. Но я ожидаю, что ваша проблема может быть перефразирована как таковая, и в этом случае у вас есть доказательство того, что у вас есть NP-полная проблема.

Answer 3

Для данного k с X и A в качестве входного принудительного принуждения, очевидно, находится в P (поскольку C (| X |, k) является многочленом в | X |).

Если к также вход, то он может зависит от «расстояний»:

Если «расстояние» произвольно, то ваша задача эквивалентна найти клику фиксированного размера в графе (который является NP-полным) :

NP-Твердость:

Возьмет экземпляр кликова задачи, то есть граф (G, Е) и целое число к. Добавьте к этому графику вершину 'a', связанную с каждой другой вершиной, пусть (G ', E') - ваш модифицированный граф.

(G ', E') k + 1 является эквивалентным экземпляром вашего первого экземпляра проблемы клики.

Создать карту Phi из G 'в R^d (вы можете сопоставить G' на N в любом случае ...) и определить «расстояние» таким образом, чтобы расстояние (Phi (c), Phi (d ')) = 1 если (c, d) ⊆ E ', 0 в противном случае.

X = Phi (G '), A = Phi ({a}), k + 1 дает вам пример вашей проблемы.

Вы можете заметить, что по конструкции s ≠ Phi (a) < => расстояние (s, Phi (A)) = 1 = максимальное расстояние (.,.), То есть min_ {s⊆S, s '≠ s ⊆ S∪A} расстояние (s, s ') = min_ {s⊆S, s' ≠ s ⊆ S} расстояние (s, s '), если | S | = k> = 2

Решите этот случай (X, A, k + 1) своей проблемы: это дает вам набор S мощности k + 1, такой, что min (distance (s, s ') | s, s'⊆ S, s ≠ s ') является максимальным.

Проверьте, есть ли s, s'⊆ S, s ≠ S', расстояние (s, s') = 0 (это может быть сделано в к^2, как | S | = к):

• Если это так, то нет набора мощности k + 1, что для всех s, s 'distance (s, s') = 1 ieнет подграфа G ', который является k + 1-clique
• , если это не так, тогда отобразите обратно S в G', по определению «расстояние» есть ребро между любыми вершинами Phi^-1 (S): это k + 1 клика

Это решение с полиномиальным уменьшением проблемы, эквивалентной проблеме клики (известной как NP-hard).

NP-Лёгкость:

Пусть X, A, K быть экземпляром вашей проблемы.

Для любого подмножества S из X min_ {s⊆S, s '≠ s ⊆ S∪A} расстояние (s, s') может принимать только значение {расстояние (x, y), x, y ⊆ X }, который имеет полиномиальный кардинал.

Чтобы найти набор, который максимизирует это расстояние, мы просто проверим все возможные расстояния для правильного набора в порядке убывания.

Чтобы проверить расстояние d, сначала сведем X к X ', содержащему только точки на расстоянии> = d от A (самой точки).

Затем мы создаем график (X ', E) ¤ где (s, s') ⊆ E, если расстояние (s, s ')> = d.

Протестируйте этот график для k-clique (это NP-easy), по построению есть один, если там есть вершины S - это множество с min_ {s⊆S, s '≠ s ⊆ S∪A} расстояние (s, S')> = d

---

Если „расстояние“ является евклидовой или иметь какие-либо забавное свойство может быть в P, я не знаю, но я не буду надеяться слишком много, если я вам.

¤ Я предположил, что Х (и, следовательно, Х ') была конечна здесь