Том 5, серия 1, номер 1, 1998 г., Стр. 60-63

УДК 519.8
М. И. Свириденко
Приближенный алгоритм для решения задачи о $p$-центре с неравенством треугольника

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

Свириденко М. И. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 23 апреля 1997 г.
Исправленный вариант — 11 февраля 1998 г.