Метрический k-центр

Комбинаторная задача оптимизации

В теории графов метрическая задача k -центра или задача вершинного k-центра является классической комбинаторной оптимизационной задачей, изучаемой в теоретической информатике , которая является NP-трудной . При наличии n городов с указанными расстояниями требуется построить k складов в разных городах и минимизировать максимальное расстояние от города до склада. В теории графов это означает нахождение набора из k вершин , для которого наибольшее расстояние любой точки до ее ближайшей вершины в k -наборе является минимальным. Вершины должны находиться в метрическом пространстве , обеспечивая полный граф , который удовлетворяет неравенству треугольника . Он применяется в размещении объектов и кластеризации . ^{[1] [2]}

Формальное определение

Впервые эта задача была предложена Хакими в 1964 году. ^[3]

Пусть будет метрическим пространством, где есть множество и есть метрика Множество , предоставляется вместе с параметром . Цель состоит в том, чтобы найти подмножество с таким, чтобы максимальное расстояние от точки в до ближайшей точки в было минимальным. Задача может быть формально определена следующим образом: Для метрического пространства ( ,d), ${\displaystyle (X,d)}$ ${\displaystyle X}$ ${\displaystyle d}$
${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }$ ${\displaystyle |{\mathcal {C}}|=k}$ ${\displaystyle \mathbf {V} }$ ${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {X}}}$

• Входные данные : набор и параметр . ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$ ${\displaystyle k}$
• Выход : набор точек . ${\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }$ ${\displaystyle k}$
• Цель : Минимизировать стоимость d(v, ) ${\displaystyle r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}}$ ${\displaystyle {\mathcal {C}}}$

То есть каждая точка в кластере находится на расстоянии не более чем от своего соответствующего центра. ^[4] ${\displaystyle r^{\mathcal {C}}(V)}$

Задача кластеризации k-центров может быть также определена на полном неориентированном графе G  = ( V ,  E ) следующим образом:
дан полный неориентированный граф G  = ( V ,  E ) с расстояниями d ( v _i ,  v _j ) ∈  N , удовлетворяющими неравенству треугольника, найти подмножество C  ⊆  V с | C | =  k , минимизируя при этом:

${\displaystyle \max _{v\in V}\min _{c\in C}d(v,c)}$

Сложность вычислений

В полном неориентированном графе G  = ( V ,  E ), если мы отсортируем ребра в порядке неубывания расстояний: d ( e ₁ ) ≤  d ( e ₂ ) ≤ ... ≤  d ( e _m ) и пусть G _i  = (V,  E _i ), где E _i  = { e ₁ ,  e ₂ , ...,  e _i }. Задача k -центра эквивалентна нахождению наименьшего индекса i такого, что G _i имеет доминирующее множество размера не более k . ^[5]

Хотя Dominating Set является NP-полным , задача k -центра остается NP-трудной . Это ясно, поскольку оптимальность данного допустимого решения для задачи k -центра может быть определена через сокращение Dominating Set, только если мы знаем в первую очередь размер оптимального решения (т. е. наименьший индекс i такой, что G _i имеет доминирующее множество размера не более k ), что как раз и является сложным ядром NP -трудных задач. Хотя сокращение Тьюринга может обойти эту проблему, перебирая все значения k .

Приближения

Простой жадный алгоритм

Простой жадный алгоритм аппроксимации , который достигает коэффициента аппроксимации 2, строится с использованием обхода farthest-first в k итерациях. Этот алгоритм просто выбирает точку, наиболее удаленную от текущего набора центров в каждой итерации, в качестве нового центра. Его можно описать следующим образом: ${\displaystyle {\mathcal {C}}}$

• Выберите произвольную точку в ${\displaystyle {\bar {c}}_{1}}$ ${\displaystyle C_{1}}$
• Для каждой точки вычислить из ${\displaystyle v\in \mathbf {V} }$ ${\displaystyle d_{1}[v]}$ ${\displaystyle {\bar {c}}_{1}}$
• Выберите точку с наибольшим расстоянием от . ${\displaystyle {\bar {c}}_{2}}$ ${\displaystyle {\bar {c}}_{1}}$
• Добавьте его к набору центров и обозначьте этот расширенный набор центров как . Продолжайте это до тех пор, пока не будет найдено k центров ${\displaystyle C_{2}}$

Продолжительность работы

• I ^-я итерация выбора i- ^го центра занимает время. ${\displaystyle {\mathcal {O}}(n)}$
• Таких итераций k .
• Таким образом, в целом алгоритм требует времени. ^[6] ${\displaystyle {\mathcal {O}}(nk)}$

Доказательство коэффициента аппроксимации

Решение, полученное с помощью простого жадного алгоритма, является 2-приближением к оптимальному решению. В этом разделе мы сосредоточимся на доказательстве этого фактора приближения.

Для заданного набора из n точек , принадлежащих метрическому пространству ( ,d), жадный алгоритм K -центров вычисляет набор K из k центров, такой что K является 2-приближением к оптимальной кластеризации V по k -центрам . ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$ ${\displaystyle {\mathcal {X}}}$

то есть ^[4] ${\displaystyle r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} ,{\textit {k}})}$

Эту теорему можно доказать, используя два случая следующим образом:

Случай 1: Каждый кластер содержит ровно одну точку ${\displaystyle {\mathcal {C}}_{opt}}$ ${\displaystyle \mathbf {K} }$

• Рассмотрим момент ${\displaystyle v\in \mathbf {V} }$
• Пусть будет центром, к которому он принадлежит ${\displaystyle {\bar {c}}}$ ${\displaystyle {\mathcal {C}}_{opt}}$
• Пусть будет центр того , что находится в ${\displaystyle {\bar {k}}}$ ${\displaystyle \mathbf {K} }$ ${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$
• ${\displaystyle d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)}$
• Сходным образом, ${\displaystyle d({\bar {k}},{\bar {c}})=d({\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}}$
• По неравенству треугольника: ${\displaystyle d(v,{\bar {k}})\leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}}$

Случай 2: Имеется два центра , и оба из них находятся в , для некоторых (по принципу классификации это единственная другая возможность) ${\displaystyle {\bar {k}}}$ ${\displaystyle {\bar {u}}}$ ${\displaystyle \mathbf {K} }$ ${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$ ${\displaystyle {\bar {c}}\in {\mathcal {C}}_{opt}}$

• Предположим, без потери общности, что это было добавлено позже к центральному множеству жадным алгоритмом, скажем, на i ^-й итерации. ${\displaystyle {\bar {u}}}$ ${\displaystyle \mathbf {K} }$
• Но поскольку жадный алгоритм всегда выбирает точку, наиболее удаленную от текущего набора центров, то мы имеем, что и, ${\displaystyle {\bar {k}}\in {\mathcal {C}}_{i-1}}$

${\displaystyle {\begin{aligned}r^{\mathbf {K} }(\mathbf {V} )\leq r^{{\mathcal {C}}_{i-1}}(\mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}},{\bar {k}})\\&\leq d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}})\\&\leq 2r^{opt}\end{aligned}}}$^[4]

Еще один алгоритм двухфакторной аппроксимации

Другой алгоритм с тем же коэффициентом аппроксимации использует тот факт, что задача k -центра эквивалентна нахождению наименьшего индекса i, такого, что G _i имеет доминирующее множество размера не более k , и вычисляет максимальное независимое множество G i _, ища наименьший индекс i , который имеет максимальное независимое множество размера не менее k . ^[7] Невозможно найти алгоритм аппроксимации с коэффициентом аппроксимации 2 − ε для любого ε > 0, если только P = NP. ^[8] Более того, расстояния всех ребер в G должны удовлетворять неравенству треугольника, если задача k -центра должна быть аппроксимирована с любым постоянным множителем, если только P = NP. ^[9]

Параметризованные аппроксимации

Можно показать, что задача k -центра W[2]-трудна для аппроксимации с точностью до множителя 2 − ε для любого ε > 0 при использовании k в качестве параметра. ^[10] Это также верно при параметризации по размерности удвоения (фактически размерности манхэттенской метрики ), если только P=NP . ^[11] При рассмотрении объединенного параметра, заданного k и размерностью удвоения , задача k -центра по-прежнему W[1]-трудна, но можно получить параметризованную схему аппроксимации . ^[12] Это возможно даже для варианта с пропускной способностью вершин, который ограничивает количество вершин, которые могут быть назначены открытому центру решения. ^[13]

Алгоритмы аппроксимации

Если , то задача k -центра вершины не может быть (оптимально) решена за полиномиальное время. Однако существуют некоторые алгоритмы аппроксимации за полиномиальное время , которые дают решения, близкие к оптимальным. В частности, 2-приближенные решения . На самом деле, если наилучшим возможным решением, которое может быть достигнуто алгоритмом за полиномиальное время, является 2-приближенное решение. ^{[14] [15] [16] [17]} В контексте задачи минимизации, такой как задача k -центра вершины, 2-приближенное решение — это любое решение, такое что , где — размер оптимального решения. Алгоритм, который гарантирует генерацию 2-приближенных решений, известен как алгоритм 2-приближения. Основными 2-приближенными алгоритмами для задачи k -центра вершины, описанными в литературе, являются алгоритм Sh, ^[18] алгоритм HS, ^[17] и алгоритм Gon. ^{[15] [16]} Несмотря на то, что эти алгоритмы являются наилучшими (полиномиальными) из возможных, их производительность на большинстве наборов данных для эталонных тестов очень недостаточна. Из-за этого со временем было разработано много эвристик и метаэвристик . Вопреки здравому смыслу, одна из самых практичных (полиномиальных) эвристик для задачи вершины k -центра основана на алгоритме CDS, который является алгоритмом 3-приближения ^[19] ${\displaystyle P\neq NP}$ ${\displaystyle P\neq NP}$ ${\displaystyle C'}$ ${\displaystyle r(C')\leq 2\times r({\text{OPT}})}$ ${\displaystyle r({\text{OPT}})}$

Алгоритм Ш.

Формально описанный Дэвидом Шмойсом в 1995 году ^[18], алгоритм Sh принимает в качестве входных данных полный неориентированный граф , положительное целое число и предположение о том, каков оптимальный размер решения. Алгоритм Sh работает следующим образом: выбирает первый центр случайным образом. До сих пор решение состоит только из одной вершины, . Затем выбирает центр случайным образом из набора, содержащего все вершины, расстояние от которых больше . В этот момент, . Наконец, выбирает оставшиеся центры тем же способом, которым были выбраны. Сложность алгоритма Sh равна , где — количество вершин. ${\displaystyle G=(V,E)}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle c_{1}}$ ${\displaystyle C=\{c_{1}\}}$ ${\displaystyle c_{2}}$ ${\displaystyle C}$ ${\displaystyle 2\times r}$ ${\displaystyle C=\{c_{1},c_{2}\}}$ ${\displaystyle k-2}$ ${\displaystyle c_{2}}$ ${\displaystyle O(kn)}$ ${\displaystyle n}$

Алгоритм HS

Предложенный Дорит Хохбаум и Дэвидом Шмойсом в 1985 году, алгоритм HS берет алгоритм Sh в качестве основы. ^[17] Заметив, что значение должно быть равно стоимости некоторого ребра в , и поскольку есть ребра в , алгоритм HS в основном повторяет алгоритм Sh с каждой стоимостью ребра. Сложность алгоритма HS составляет . Однако, запустив бинарный поиск по упорядоченному набору стоимостей ребер, его сложность снижается до . ${\displaystyle r({\text{OPT}})}$ ${\displaystyle E}$ ${\displaystyle O(n^{2})}$ ${\displaystyle E}$ ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{2}\log n)}$

Алгоритм Гона

Предложенный независимо Теофило Гонсалесом ^[15] и Мартином Дайером и Аланом Фризом ^[16] в 1985 году, алгоритм Гона по сути является более мощной версией алгоритма Ш. В то время как алгоритм Ш требует предположения о , алгоритм Гона отказывается от такого предположения, замечая, что если существует какой-либо набор вершин на расстоянии большем, чем , то самая дальняя вершина должна находиться внутри такого набора. Поэтому вместо вычисления на каждой итерации набора вершин на расстоянии большем, чем , а затем выбора случайной вершины, алгоритм Гона просто выбирает самую дальнюю вершину из каждого частичного решения . Сложность алгоритма Гона равна , где — количество вершин. ${\displaystyle r}$ ${\displaystyle r({\text{OPT}})}$ ${\displaystyle 2\times r({\text{OPT}})}$ ${\displaystyle 2\times r}$ ${\displaystyle C'}$ ${\displaystyle O(kn)}$ ${\displaystyle n}$

Алгоритм CDS

Предложенный Гарсией Диасом и др. в 2017 году ^[19], алгоритм CDS представляет собой алгоритм с 3 приближениями, который использует идеи из алгоритма Gon (эвристика самой дальней точки), алгоритма HS (параметрическое отсечение) и взаимосвязи между проблемой k -центра вершины и проблемой доминирующего множества . Алгоритм CDS имеет сложность . Однако, выполняя бинарный поиск по упорядоченному набору стоимостей ребер, предлагается более эффективная эвристика под названием CDSh. Сложность алгоритма CDSh составляет . Несмотря на неоптимальную производительность алгоритма CDS и эвристическую производительность CDSh, оба они демонстрируют гораздо лучшую производительность, чем алгоритмы Sh, HS и Gon. ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{2}\log n)}$

Параметризованные аппроксимации

Можно показать, что задача k -центра W[2]-трудна для аппроксимации с точностью до множителя 2 − ε для любого ε > 0 при использовании k в качестве параметра. ^[20] Это также верно при параметризации с помощью удвоения размерности (фактически размерности манхэттенской метрики ), если только P=NP . ^[21] При рассмотрении объединенного параметра, заданного k и удвоением размерности , k -центр все еще W[1]-труден, но можно получить параметризованную схему аппроксимации . ^[22] Это возможно даже для варианта с емкостями вершин, которые ограничивают, сколько вершин может быть назначено открытому центру решения. ^[23]

Экспериментальное сравнение

Некоторые из наиболее широко используемых наборов данных для эталонной задачи вершинного центра k — это экземпляры pmed из OR-Lib. ^[24] и некоторые экземпляры из TSP-Lib. ^[25] В таблице 1 показано среднее и стандартное отклонение экспериментальных коэффициентов аппроксимации решений, сгенерированных каждым алгоритмом по 40 экземплярам pmed из OR-Lib ^[19].

Полиномиальная эвристика

Жадный чистый алгоритм

Жадный чистый алгоритм (или Gr) следует основной идее жадных алгоритмов : принимать оптимальные локальные решения. В случае задачи вершины k -центра оптимальное локальное решение состоит в выборе каждого центра таким образом, чтобы размер решения (радиус покрытия) был минимальным на каждой итерации. Другими словами, первый выбранный центр - это тот, который решает задачу с 1 центром. Второй выбранный центр - это тот, который вместе с предыдущим центром генерирует решение с минимальным радиусом покрытия. Остальные центры выбираются таким же образом. Сложность алгоритма Gr составляет . ^[26] Эмпирическая производительность алгоритма Gr плохая на большинстве эталонных экземпляров. ${\displaystyle O(kn^{2})}$

Алгоритм подсчета очков

Алгоритм подсчета очков (или Scr) был представлен Юрием Михеличем и Борутом Робичем в 2005 году. ^[27] Этот алгоритм использует преимущество сведения от задачи вершинного k -центра к задаче минимального доминирующего множества. Задача решается путем обрезки входного графа со всеми возможными значениями оптимального размера решения и последующего эвристического решения задачи минимального доминирующего множества. Эта эвристика следует ленивому принципу, который принимает каждое решение как можно медленнее (в отличие от жадной стратегии). Сложность алгоритма Scr составляет . Эмпирическая производительность алгоритма Scr очень хороша на большинстве эталонных экземпляров. Однако его время работы быстро становится непрактичным по мере роста входных данных. Таким образом, это, по-видимому, хороший алгоритм только для небольших экземпляров. ${\displaystyle O(n^{4})}$

Смотрите также

• Задача коммивояжера
• Минимальный k-разрез
• Доминирующий набор
• Независимое множество (теория графов)
• Проблема расположения объекта

Ссылки

1. Пачеко, Хоакин А.; Касадо, Сильвия (декабрь 2005 г.). «Решение двух моделей местоположений с небольшим количеством учреждений с использованием гибридной эвристики: случай реальных ресурсов здравоохранения». Computers & Operations Research . 32 (12): 3075–3091. doi :10.1016/j.cor.2004.04.009. ISSN  0305-0548.
2. Кавех, А.; Наср, Х. (август 2011 г.). «Решение проблемы условного и безусловного -центра с помощью поиска модифицированной гармонии: реальный пример». Scientia Iranica . 18 (4): 867–877. doi : 10.1016/j.scient.2011.07.010 . ISSN  1026-3098.
3. Хакими, С. Л. (1964). «Оптимальные расположения центров коммутации и абсолютные центры и медианы графа». Исследование операций . 12 (3): 450–459. doi :10.1287/opre.12.3.450. JSTOR  168125.
4. Har-peled, Sariel (2011). Геометрические алгоритмы аппроксимации . Бостон, Массачусетс, США: Американское математическое общество. ISBN 978-0821849118.
5. Вазирани, Виджай В. (2003), Алгоритмы аппроксимации , Берлин: Springer, стр. 47–48, ISBN 3-540-65367-8
6. Гонсалес, Теофило Ф. (1985), «Кластеризация для минимизации максимального межкластерного расстояния», Теоретическая информатика , т. 38, Elsevier Science BV, стр. 293–306, doi : 10.1016/0304-3975(85)90224-5
7. Хохбаум, Дорит С.; Шмойс , Дэвид Б. (1986), «Единый подход к аппроксимационным алгоритмам для проблем с узкими местами», Журнал ACM , т. 33, стр. 533–550, doi :10.1145/5925.5933, ISSN  0004-5411, S2CID  17975253
8. Хохбаум, Дорит С. (1997), Аппроксимационные алгоритмы для NP-трудных задач , Бостон: PWS Publishing Company, стр. 346–398, ISBN 0-534-94968-1
9. Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Вегингер, Герхард (2000), «Минимальный k-центр», Сборник задач оптимизации NP
10. Фельдманн, Андреас Эмиль (2019-03-01). "Приближения с фиксированными параметрами для задач k-центра в графах малой размерности шоссе" (PDF) . Algorithmica . 81 (3): 1031–1052. doi :10.1007/s00453-018-0455-0. ISSN  1432-0541. S2CID  46886829.
11. Федер, Томас; Грин, Дэниел (1988-01-01). "Оптимальные алгоритмы для приблизительной кластеризации". Труды двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. doi :10.1145/62212.62255. ISBN 978-0-89791-264-8. S2CID  658151.
12. Фельдманн, Андреас Эмиль; Маркс, Даниэль (2020-07-01). «Параметризованная сложность проблемы k-центра в транспортных сетях» (PDF) . Algorithmica . 82 (7): 1989–2005. doi :10.1007/s00453-020-00683-w. ISSN  1432-0541. S2CID  3532236.
13. Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $$k$$-центр: различение удвоения и измерения шоссе». В Bekos, Michael A.; Кауфманн, Майкл (ред.). Графовые концепции в информатике . Конспект лекций по информатике. Том 13453. Cham: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . doi :10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.
14. Карив, О.; Хакими, С.Л. (декабрь 1979 г.). «Алгоритмический подход к проблемам размещения в сети. I: p-центры». Журнал SIAM по прикладной математике . 37 (3): 513–538. doi :10.1137/0137040. ISSN  0036-1399.
15. Гонсалес, Теофило Ф. (1985). «Кластеризация для минимизации максимального межкластерного расстояния». Теоретическая информатика . 38 : 293–306. doi : 10.1016/0304-3975(85)90224-5 . ISSN  0304-3975.
16. Дайер, ME; Фриз, AM (февраль 1985). "Простая эвристика для проблемы p-центра". Operations Research Letters . 3 (6): 285–288. doi :10.1016/0167-6377(85)90002-1. ISSN  0167-6377.
17. Хохбаум, Дорит С .; Шмойс, Дэвид Б. (май 1985). «Лучшая возможная эвристика для проблемы k -центра». Математика исследования операций . 10 (2): 180–184. doi :10.1287/moor.10.2.180. ISSN  0364-765X.
18. Shmoys, David B. (1995). "Вычисление почти оптимальных решений для задач комбинаторной оптимизации". Комбинаторная оптимизация . Серия DIMACS по дискретной математике и теоретической информатике. Том 20. С. 355–397. CiteSeerX 10.1.1.33.1719 . doi :10.1090/dimacs/020/07. ISBN  9780821802397.
19. Гарсия-Диас, Иисус; Санчес-Эрнандес, Хаиро; Менчака-Мендес, Рикардо; Менчака-Мендес, Роландо (2017-07-01). «Когда худший фактор аппроксимации дает лучшую производительность: алгоритм 3-аппроксимации для задачи вершинного k -центра». Журнал эвристики . 23 (5): 349–366. doi :10.1007/s10732-017-9345-x. ISSN  1381-1231. S2CID  254500532.
20. Фельдманн, Андреас Эмиль (2019-03-01). «Аппроксимации с фиксированными параметрами для задач k-центра в графах малой размерности шоссе». Algorithmica . 81 (3): 1031–1052. arXiv : 1605.02530 . doi :10.1007/s00453-018-0455-0. ISSN  1432-0541. S2CID  46886829.
21. Федер, Томас; Грин, Дэниел (1988-01-01). "Оптимальные алгоритмы для приблизительной кластеризации". Труды двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. doi :10.1145/62212.62255. ISBN 978-0-89791-264-8. S2CID  658151.
22. Фельдманн, Андреас Эмиль; Маркс, Даниэль (01.07.2020). «Параметризованная сложность проблемы k-центра в транспортных сетях». Algorithmica . 82 (7): 1989–2005. arXiv : 1802.08563 . doi : 10.1007/s00453-020-00683-w. ISSN  1432-0541. S2CID  3532236.
23. Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $$k$$-центр: различение удвоения и измерения шоссе». В Bekos, Michael A.; Кауфманн, Майкл (ред.). Графовые концепции в информатике . Конспект лекций по информатике. Том 13453. Cham: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . doi :10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.
24. Бисли, Дж. Э. (1990). «OR-Library: Распространение тестовых задач по электронной почте». Журнал Общества операционных исследований . 41 (11): 1069–1072. doi :10.2307/2582903. JSTOR  2582903.
25. Райнелт, Герхард (ноябрь 1991 г.). «TSPLIB — Библиотека задач коммивояжера». Журнал ORSA по вычислениям . 3 (4): 376–384. doi :10.1287/ijoc.3.4.376. ISSN  0899-1499.
26. Рана, Раттан; Гарг, Дипак (март 2009 г.). «Эвристические подходы к проблеме K-центра». Международная конференция IEEE по передовым вычислениям 2009 г. IEEE. стр. 332–335. doi :10.1109/iadcc.2009.4809031. ISBN 9781424429271. S2CID  12453616.
27. Михелич, Юрий; Робич, Борут (2005). «Эффективное решение проблемы k-центра с помощью алгоритма доминирующего множества». Журнал вычислительной техники и информационных технологий . 13 (3): 225. CiteSeerX 10.1.1.205.3118 . doi : 10.2498/cit.2005.03.05 . ISSN  1330-1136. 

Дальнейшее чтение

• Хохбаум, Дорит С.; Шмойс , Дэвид Б. (1985), «Лучшая возможная эвристика для проблемы k-центра», Математика исследования операций , т. 10, стр. 180–184, doi :10.1287/moor.10.2.180