Hardprob/Minimum K-Center — различия между версиями

Версия 19:59, 10 апреля 2023

Полный граф и расстояния , удовлетворяющие неравенству треугольника.
Найти к-центр, т.е. подмножество , с минимальным расстоянием от всех вершин до какого-то узла из этого множества.
Минимизировать максимальное расстояние от каждой вершины до ближайшего к ней «центра»:

@@ Строка 1: / Строка 1: @@
-<!-- start -->
+<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Полный граф <m>G=\left(V,E\right)</m> и расстояния <m>d(v_i,v_j)\in N</m>, удовлетворяющие неравенству треугольника.
 * Найти [https://en.wikipedia.org/wiki/Metric_k-center к-центр], т.е. подмножество <m>C \subseteq V, \vert C\vert=k</m>, с минимальным расстоянием от всех вершин до какого-то узла из этого множества.