Приближенный алгоритм нахождения кратных медиан графа
Тэйц и Барт предложили эвристический метод для нахождения р-медианы. Метод состоит в следующем: случайным образом выбираются р вершин, они и образуют начальное множество S, аппроксимирующее р-медианное множество 
.
заменить вершину 
, для чего строится новое множество 
и сравниваются передаточные числа 
и 
. Если 
, то вершина 
замещается вершиной 
и из множества S получается множество 
, которое лучше аппроксимирует р-медианное множество . Затем исследуется и преобразуется множество , по вышеприведенной процедуре до тех пор, пока не будет построено множество 
, такое, что ни одну его вершину нельзя заместить вершинной из множества 
и получить множество с меньшим передаточным числом, чем 
. Множество S* берется в качестве требуемого приближения к множеству . Описание приближенного алгоритма:
Шаг 1. Выбрать некоторое множество S из р вершин в качестве начального приближения к р-медиане. Назовем все вершины "неопробованными".
Шаг 2. Взять произвольную «неопробованную» вершину и для каждой вершины вычислить "приращение" 
, соответствующее замене вершины 
вершиной 
, т.е. вычислить
.
Шаг 3. Найти 
.
1. Если 
, то назвать вершину "опробованной".
2. Если 
, то 
и назвать все вершины множества 
"неопробованными".
Шаг 4. Если все вершины из множества опробованы, то конец алгоритма (текущее множество S является аппроксимацией р-медианного множества ), иначе перейти к шагу 2.
Этот алгоритм можно применить для нахождения р-центра.