選擇具有最小可能直徑的k個點

Question

給定一組n點和n x n距離矩陣，我該如何精確選擇這些點的k，以使直徑（任意兩個選定點之間的最大距離）最小化？距離度量服從三角不等式，但不一定是歐氏距離或minkowski距離。我們可以假設所有的距離是兩兩不同的。

此外，我想解決這個問題的範圍內的所有k值n - 1, n - 2, ... n - d。我知道這可以做得比檢查每個k的所有n choose k組合更快，但我提出的解決方案仍然不是很有效率（我很確定多項式時間解決方案不存在，但我想知道是否有可能做得更好）。

我唯一的方法是遞歸的。找到它們之間距離最大的兩個點p1和p2（首先按距離對所有對進行排序）。然後k = n - 1案例是由所有點減去p1或p2組成的集合之一。一個可能比另一個更好，或者可能是平局。 k < n - 1的所有解決方案必須是其中一個集合的子集（不能同時包含p1和p2），但不一定是獲勝的解決方案。繼續檢查這兩組的子集。我認爲這是類似於O(n^2 log n + 2^d)，但這仍然比檢查每個k到n - d的所有組合都要好，只要d足夠小（我認爲至少爲k/2）。

一個相關的問題 - 找到直徑不大於t的最大子集 - 等於independent set problem（以距離大於t的邊緣爲邊界的圖），但這已知爲NP-hard。

這些解決方案都沒有利用三角形不等式，這給我留下了一點希望，即存在更有效的解決方案。

Answer 1

服從三角形不等式的度量標準應該能夠支持https://en.wikipedia.org/wiki/Cover_tree。如果實際上度量與低維空間大致相同，這將節省搜索近點的時間。

鑑於此，我將運行分支和邊界搜索，遞歸搜索所有（n個選擇k個）可能性，但通過從覆蓋樹中可逆地刪除子樹來儘快丟棄部分解。在搜索的每個階段，您都有一段距離，相當於迄今爲止找到的最佳答案（開始時可能是無限或猜測）。當您爲當前的部分解決方案添加一個點時，可以從覆蓋樹中可逆地刪除子樹，其中只包含距離剛剛添加的點的距離大於或等於當前最佳距離的點。對於覆蓋樹，您可以使用三角不等式的推導來檢查：d（a，b）+ d（b，c）> = d（a，c）意味着d（a，b）> = d a，c） - d（b，c）。如果發現剩餘封面樹中沒有足夠的點來完成當前的部分解決方案，則可以從遞歸的那一部分返回。

Answer 2

有關與所有的距離可比所有DS：

考慮graph，其頂點集是您點的集合，其邊緣
是對{P，Q}，使得距離在這些點之間是大於比D大。
一組點具有至多D的直徑當且僅當它的補碼是vertex cover。


因此，你的問題是NP難的，但是當NK參數變得
固定參數可解：

與 this algorithm

使用二進制搜索以確定
最低的間隙間的距離是d可以在什麼位置以及缺失點實現那個差距。