algorithm - 找到使 S 并 A 中的点之间的最小距离最大化的集合 S

Question

我想找到给定基数k的集合S，最大化每个点与给定集合A之间的最小距离。有没有一个简单的算法来找到这个最大最小问题的解决方案？

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

谢谢!

Answer 1

对于给定的 k，以 X 和 A 作为输入，暴力破解显然在 P 中(因为 C(|X|,k) 是 |X| 中的多项式)。

如果 k 也是一个输入，那么它可能取决于“距离”:

如果“距离”是任意的，那么你的问题相当于在图中找到一个固定大小的团(这是 NP 完全的):

NP 硬度:

以团问题为例，即一个图 (G​​,E) 和一个整数 k。 向该图中添加一个与其他每个顶点相连的顶点“a”，令 (G',E') 为修改后的图。

(G',E') k+1 就是第一个团问题实例的等效实例。

创建从 G' 到 R^d 的映射 Phi(无论如何，您都可以将 G' 映射到 N 上...)并定义“距离”，使得距离(Phi(c),Phi(d')) = 1 如果(c,d) ⊆ E'，否则为 0。

X = Phi(G'), A = Phi({a}), k+1 为您提供问题的一个实例。

你可以注意到，通过构造 s ≠ Phi(a) <=> distance(s,Phi(A)) = 1 = max distance(.,.)，即 min_{s⊆S, s'≠s ⊆ S∪A} 距离(s,s') = min_{s⊆S, s'≠s ⊆ S} 距离(s,s') if |S| = k >= 2

解决问题的这个实例 (X,A,k+1) :这给你一个基数为 k+1 的集合 S，使得 min( distance(s,s') |s,s'⊆ S, s ≠s') 最大。

检查是否存在 s,s'⊆ S, s≠s', distance(s,s') = 0(这可以在 k^2 中完成，如 |S| = k):

• 如果是这种情况，则不存在基数 k+1 的集合，使得对于所有 s,s' 距离(s,s') = 1，即不存在 G' 的子图，它是 k+1-clique
• 如果不是这种情况，则将 S 映射回 G'，根据“距离”的定义，Phi^-1 (S) 的任何顶点之间都有一条边:这是一个 k+1 派

这通过多项式约简解决了与团问题等价的问题(称为 NP 困难)。

NP-简易性:

让 X、A、k 成为问题的一个实例。

对于 X min_{s⊆S, s'≠s ⊆ S∪A} 的任何子集 S，距离(s,s') 只能在 {distance(x,y), x,y ⊆ X} 中取值-有一个多项式基数-。

为了找到一个使该距离最大化的集合，我们只需按降序测试正确集合的每个可能距离。

为了测试距离 d，我们首先将 X 减少到 X'，其中仅包含 A{点本身} 距离 >= d 的点。

然后我们创建一个图 (X',E) ¤ 其中 (s,s') ⊆ E 当且仅当距离(s,s') >= d。

测试这个图的 k-clique(它是 NP-easy)，通过构造有一个当且仅当它的顶点 S 是一组 min_{s⊆S, s'≠s ⊆ S∪A} 距离(s ,s') >= d

---

如果“距离”是欧几里得或者有任何有趣的属性，它可能在 P 中，我不知道，但如果我是你，我不会抱太大希望。

¤ 我假设 X(因此 X')在这里是有限的