Приближенный алгоритм для решения задачи о $p$-центре с неравенством треугольника

Рассматривается взвешенная задача о $p$-центре, когда матрица расстояний удовлетворяет неравенству треугольника, т. е. для всех $i$, $j$, $k$ выполняется неравенство $d_{ij}+d_{jk}\geqslant d_{ik}$. В [2] для приближенного решения этой задачи предлагается алгоритм с относительной погрешностью $\rho=3$, временная сложность которого не превосходит величины $O(n^2\log_2n)$. В настоящей работе предлагается алгоритм с той же погрешностью и временной сложностью $O(n^2)$. Библиогр. 3.