2

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

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')

谢谢 ！

4

3 回答 3

3

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

如果 k 也是一个输入，那么它可能取决于 'distance' ：

如果“距离”是任意的，那么您的问题相当于在图中找到一个固定大小的集团（这是 NP 完全的）：

NP-硬度：

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

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

创建一个从 G' 到 R^d 的映射 Phi（无论如何您都可以将 G' 映射到 N ...）并定义“距离”，使得距离（Phi(c),Phi(d')) = 1 if (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') 如果 |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' distance(s,s') = 1 即不存在 G' 的子图，它是 k+1-clique
  • 如果不是这种情况，则将 S 映射回 G'，根据“距离”的定义，Phi^-1 (S) 的任何顶点之间都有一条边：这是一个 k+1 集团

这通过多项式归约解决了与团问题（称为 NP-hard）等效的问题。

NP-容易：

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

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

为了找到一个最大化这个距离的集合，我们将按降序测试正确集合的所有可能距离。

为了测试距离 d，我们首先将 X 简化为仅包含距离 >= d 的 A{点本身} 的点。

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

测试这个图的k-clique（它是NP-easy），通过构造有一个如果它的顶点S是一组具有min_{s⊆S，s'≠s⊆S∪A}距离（s，s' ) >= d

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

¤ 我假设 X（因此 X'）在这里是有限的

于 2012-06-12T21:13:21.370 回答
1

搜索的前 2 个结果sphere packing np complete出现了对 1981 年论文的引用，该论文证明了 2d 中的最佳打包和覆盖是 np 完整的。我没有访问研究图书馆的权限，所以我无法阅读论文。但我希望你的问题可以改写为那个问题，在这种情况下，你有证据证明你有一个 NP 完全问题。

于 2012-06-12T17:36:58.763 回答
1

这可能是 NP 难的。贪婪地选择离先前选择最远的点是 2 近似值。基于 Arora 和 Mitchell 的 Euclidean TSP 方案，可能有一个复杂的低 d 近似方案。对于 d = 10，忘记它。

于 2012-06-12T16:02:06.863 回答