Эвристический метод для нахождения p-медианы состоит в следующем: случайным образом выбираются p {\displaystyle p} вершин, они образуют начальное множество S {\displaystyle S} , аппроксимирующее p-медианное множество X p ∗ {\displaystyle X_{p}^{*}} . Затем выясняется, может ли некоторая вершина x j ∈ X ∖ S {\displaystyle x_{j}\in X\setminus S} заменить вершину x i ∈ S {\displaystyle x_{i}\in S} (как медианная вершина), для чего строят новое множество S ∗ = ( S ∪ x j ) ∖ x i {\displaystyle S^{*}=(S\cup {x_{j}})\setminus {x_{i}}} и сравнивают передаточные числа σ ( S ∗ ) {\displaystyle \sigma (S^{*})} и σ ( S ) {\displaystyle \sigma (S)} . Если σ ( S ∗ ) < σ ( S ) {\displaystyle \sigma (S^{*})<\sigma (S)} , то S {\displaystyle S} заменяют на S ∗ {\displaystyle S^{*}} , которое лучше аппроксимирует p-медианное множество X p ∗ {\displaystyle X_{p}^{*}} . Затем аналогично исследуется множество S ∗ {\displaystyle S^{*}} и т. д., пока не будет построено множество S {\displaystyle S} ', которое нельзя будет изменить по вышеуказанному принципу.
Шаг 1. Выбрать некоторое множество S {\displaystyle S} из p вершин в качестве начального приближения к p-медиане. И назовём все вершины x i ∉ S {\displaystyle x_{i}\notin S} «неопробованными».
Шаг 2. Взять произвольную «неопробованную» вершину и для каждой вершины x i ∈ S {\displaystyle x_{i}\in S} вычислить «приращение» Δij, соответствующие замене вершины x i {\displaystyle x_{i}} вершиной x j {\displaystyle x_{j}} , то есть вычислить Δ i j = σ ( S ) − σ ( ( S ∪ x j ) ∖ x i ) {\displaystyle \Delta _{ij}=\sigma (S)-\sigma ((S\cup {x_{j}})\setminus {x_{i}})} .
Шаг 3. Найти Δ i 1 j = m a x [ Δ i j ] {\displaystyle \Delta _{i^{1}j}=max[\Delta _{ij}]} по всем x i ∈ S {\displaystyle x_{i}\in S} .
а) Если Δ i 1 j ≤ 0 {\displaystyle \Delta _{i^{1}j}\leq 0} , то назвать вершину x j {\displaystyle x_{j}} «опробованной» и перейти к шагу 2.
б) Если Δ i i j ≥ 0 {\displaystyle \Delta _{i^{i}j}\geq 0} , то S ← ( S ∪ x j ) ∖ x i {\displaystyle S\gets (S\cup {x_{j}})\setminus {x_{i}}} , назвать вершину x j {\displaystyle x_{j}} «опробованной» и перейти к шагу 2.
Шаг 4. Повторять шаги 2 и 3 до тех пор, пока все вершины из X ∖ S {\displaystyle X\setminus S} не будут опробованы. Эта процедура оформляется как цикл. Если при выполнении последнего цикла совсем не будет замещений вершин на шаге 3(a), то перейти к шагу 5. В противном случае, то есть если осуществлено некоторое замещение, назвать все вершины «неопробованными» и вернуться к шагу 2.
Шаг 5. Стоп. Текущее множество S {\displaystyle S} является подходящей аппроксимацией p-медианного множества X p ∗ {\displaystyle X_{p}^{*}} .
Легко заметить, что приведённый выше алгоритм не во всех случаях даёт оптимальный ответ. Рассмотрим пример (числа, стоящие около рёбер, равны соответствующим рёберным стоимостям, все вершины одинакового единичного веса):
Если искать 2-медиану и в качестве начального множества S взять {x3, x6} с передаточным числом σ ( S ) = 8 {\displaystyle \sigma (S)=8} , то никакое замещение только одной вершины не приводит к множеству с меньшим передаточным числом. Однако множество {x3, x6} не является 2-медианой данного графа, так как существуют два 2-медианных множества с передаточным числом 7: {x1, x4} и {x2, x5}.