вершин k -центра Проблема

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

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

Проблема вершин k -центра — это классическая NP-трудная задача в информатике . Впервые он был предложен Хакими в 1964 году. ^[3] Формально задача вершины k -центра состоит в том, что: дан полный неориентированный граф $G=(V,E)$ в метрическом пространстве и целое положительное число $k$ , найдите подмножество $C\subseteq V$ такой, что $|C|\leq k$ и целевая функция $r(C)=\max _{v\in V}\{d(v,C)\}$ сведен к минимуму. Расстояние $d(v,C)$ определяется как расстояние от вершины $v$ до ближайшего центра в $C$ .

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

Если $P\neq NP$ , проблема вершины k -центра не может быть (оптимально) решена за полиномиальное время. Однако существуют некоторые алгоритмы аппроксимации с полиномиальным временем , которые дают почти оптимальные решения. В частности, 2-приближенные решения . На самом деле, если $P\neq NP$ Наилучшее возможное решение, которое может быть достигнуто с помощью алгоритма с полиномиальным временем, - это 2-аппроксимированное решение. ^[4]^[5]^[6]^[7] В контексте задачи минимизации, такой как задача вершины k -центра, 2-приближенным решением является любое решение $C'$ такой, что $r(C')\leq 2\times r({\text{OPT}})$ , где $r({\text{OPT}})$ – размер оптимального решения. Алгоритм, который гарантирует генерирование 2-приближенных решений, известен как алгоритм 2-приближения. Основными 2-аппроксимированными алгоритмами решения задачи k -центра вершин, представленными в литературе, являются алгоритм Sh, ^[8] алгоритм HS, ^[7] и алгоритм Гона. ^[5]^[6] Несмотря на то, что эти алгоритмы являются (полиномиально) лучшими из возможных, их производительность на большинстве эталонных наборов данных очень недостаточна. По этой причине множество эвристик и метаэвристик с течением времени было разработано . Вопреки здравому смыслу, одна из наиболее практичных (полиномиальных) эвристик для задачи k -центра вершин основана на алгоритме CDS, который представляет собой алгоритм с 3-мя приближениями. ^[9]

Алгоритм Ш

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

Алгоритм HS

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

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

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

Алгоритм CDS

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

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

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

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

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

Таблица 1. Экспериментальный коэффициент аппроксимации по сравнению с экземплярами pmed из OR-Lib
Алгоритм	$\mu$	$\sigma$	Сложность
HS	1.532	0.175	$O(n^{2}\log n)$
Гон	1.503	0.122	$O(kn)$
ЦДШ	1.035	0.031	$O(n^{2}\log n)$
CDS	1.020	0.027	$O(n^{4})$

Таблица 2. Коэффициент экспериментальной аппроксимации для экземпляров из TSP-Lib
Алгоритм	$\mu$	$\sigma$	Алгоритм
Гон	1.396	0.091	$O(kn)$
HS	1.318	0.108	$O(n^{2}\log n)$
ЦДШ	1.124	0.065	$O(n^{2}\log n)$
CDS	1.042	0.038	$O(n^{4})$

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

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

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

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

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

Ссылки

^ Пачеко, Хоакин А.; Касадо, Сильвия (декабрь 2005 г.). «Решение двух моделей местоположения с небольшим количеством объектов с использованием гибридной эвристики: реальный случай ресурсов здравоохранения». Компьютеры и исследования операций . 32 (12): 3075–3091. дои : 10.1016/j.cor.2004.04.009 . ISSN 0305-0548 .
^ Каве, А.; Наср, Х. (август 2011 г.). «Решение проблемы условного и безусловного центра с помощью модифицированного поиска гармонии: реальный пример» . Наука Ираника . 18 (4): 867–877. doi : 10.1016/j.scient.2011.07.010 . ISSN 1026-3098 .
^ Хакими, С.Л. (1964). «Оптимальное расположение коммутационных центров, абсолютных центров и медиан графа». Исследование операций . 12 (3): 450–459. дои : 10.1287/опре.12.3.450 . JSTOR 168125 .
^ Карив, О.; Хакими, С.Л. (декабрь 1979 г.). «Алгоритмический подход к проблемам сетевого расположения. I: p-центры». SIAM Journal по прикладной математике . 37 (3): 513–538. дои : 10.1137/0137040 . ISSN 0036-1399 .
^ Jump up to: ^а ^б ^с Гонсалес, Теофило Ф. (1985). «Кластеризация для минимизации максимального расстояния между кластерами» . Теоретическая информатика . 38 : 293–306. дои : 10.1016/0304-3975(85)90224-5 . ISSN 0304-3975 .
^ Jump up to: ^а ^б ^с Дайер, Мэн; Фриз, AM (февраль 1985 г.). «Простая эвристика для проблемы p-центра». Письма об исследованиях операций . 3 (6): 285–288. дои : 10.1016/0167-6377(85)90002-1 . ISSN 0167-6377 .
^ Jump up to: ^а ^б ^с Хохбаум, Дорит С .; Шмойс, Дэвид Б. (май 1985 г.). «Наилучшая возможная эвристика для проблемы k -центра». Математика исследования операций . 10 (2): 180–184. дои : 10.1287/moor.10.2.180 . ISSN 0364-765X .
^ Jump up to: ^а ^б Шмойс, Дэвид Б. (1995). «Вычисление почти оптимальных решений задач комбинаторной оптимизации». Комбинаторная оптимизация . Серия DIMACS по дискретной математике и теоретической информатике. Том. 20. С. 355–397. CiteSeerX 10.1.1.33.1719 . дои : 10.1090/dimacs/020/07 . ISBN 9780821802397 .
^ Jump up to: ^а ^б ^с Гарсиа-Диас, Хесус; Санчес-Эрнандес, Хаиро; Менчака-Мендес, Рикардо; Менчака-Мендес, Роландо (01 июля 2017 г.). «Когда худший коэффициент аппроксимации дает лучшую производительность: алгоритм с 3 приближениями для задачи вершины k -центра». Журнал эвристики . 23 (5): 349–366. дои : 10.1007/s10732-017-9345-x . ISSN 1381-1231 . S2CID 254500532 .
^ Фельдманн, Андреас Эмиль (01 марта 2019 г.). «Аппроксимации с фиксированными параметрами для задач k-центра в графах шоссе малой размерности» . Алгоритмика . 81 (3): 1031–1052. arXiv : 1605.02530 . дои : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .
^ Федер, Томас; Грин, Дэниел (1 января 1988 г.). «Оптимальные алгоритмы приближенной кластеризации» . Материалы двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. дои : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 . S2CID 658151 .
^ Фельдманн, Андреас Эмиль; Маркс, Даниэль (01 июля 2020 г.). «Параметризованная жесткость задачи k-центра в транспортных сетях» . Алгоритмика . 82 (7): 1989–2005. arXiv : 1802.08563 . дои : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .
^ Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $$k$$-центр: различие удвоения и измерения шоссе» . В Бекосе, Майкл А.; Кауфманн, Майкл (ред.). Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 13453. Чам: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . дои : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .
^ Бизли, Дж. Э. (1990). «ИЛИ-библиотека: Распространение тестовых задач по электронной почте». Журнал Общества операционных исследований . 41 (11): 1069–1072. дои : 10.2307/2582903 . JSTOR 2582903 .
^ Рейнельт, Герхард (ноябрь 1991 г.). «TSPLIB — Библиотека задач коммивояжера». Журнал ORSA по вычислительной технике . 3 (4): 376–384. дои : 10.1287/ijoc.3.4.376 . ISSN 0899-1499 .
^ Рана, Ротанг; Гарг, Дипак (март 2009 г.). «Эвристические подходы к проблеме К-центра». 2009 Международная конференция по передовым вычислениям IEEE . IEEE. стр. 332–335. дои : 10.1109/iadcc.2009.4809031 . ISBN 9781424429271 . S2CID 12453616 .
^ Мигелич, Юрий; Робич, Борут (2005). «Эффективное решение проблемы k -центра с помощью алгоритма доминирующего множества» . Журнал вычислительной техники и информационных технологий . 13 (3): 225. doi : 10.2498/cit.2005.03.05 . ISSN 1330-1136 .

[1] Пачеко, Хоакин А.; Касадо, Сильвия (декабрь 2005 г.). «Решение двух моделей местоположения с небольшим количеством объектов с использованием гибридной эвристики: реальный случай ресурсов здравоохранения». Компьютеры и исследования операций . 32 (12): 3075–3091. дои : 10.1016/j.cor.2004.04.009 . ISSN 0305-0548 .

[2] Каве, А.; Наср, Х. (август 2011 г.). «Решение проблемы условного и безусловного центра с помощью модифицированного поиска гармонии: реальный пример» . Наука Ираника . 18 (4): 867–877. doi : 10.1016/j.scient.2011.07.010 . ISSN 1026-3098 .

[3] Хакими, С.Л. (1964). «Оптимальное расположение коммутационных центров, абсолютных центров и медиан графа». Исследование операций . 12 (3): 450–459. дои : 10.1287/опре.12.3.450 . JSTOR 168125 .

[4] Карив, О.; Хакими, С.Л. (декабрь 1979 г.). «Алгоритмический подход к проблемам сетевого расположения. I: p-центры». SIAM Journal по прикладной математике . 37 (3): 513–538. дои : 10.1137/0137040 . ISSN 0036-1399 .

[Gonzalez_1985-5] Jump up to: ^а ^б ^с Гонсалес, Теофило Ф. (1985). «Кластеризация для минимизации максимального расстояния между кластерами» . Теоретическая информатика . 38 : 293–306. дои : 10.1016/0304-3975(85)90224-5 . ISSN 0304-3975 .

[Dyer_1985-6] Jump up to: ^а ^б ^с Дайер, Мэн; Фриз, AM (февраль 1985 г.). «Простая эвристика для проблемы p-центра». Письма об исследованиях операций . 3 (6): 285–288. дои : 10.1016/0167-6377(85)90002-1 . ISSN 0167-6377 .

[Hochbaum_1985-7] Jump up to: ^а ^б ^с Хохбаум, Дорит С .; Шмойс, Дэвид Б. (май 1985 г.). «Наилучшая возможная эвристика для проблемы k -центра». Математика исследования операций . 10 (2): 180–184. дои : 10.1287/moor.10.2.180 . ISSN 0364-765X .

[Shmoys_1995-8] Jump up to: ^а ^б Шмойс, Дэвид Б. (1995). «Вычисление почти оптимальных решений задач комбинаторной оптимизации». Комбинаторная оптимизация . Серия DIMACS по дискретной математике и теоретической информатике. Том. 20. С. 355–397. CiteSeerX 10.1.1.33.1719 . дои : 10.1090/dimacs/020/07 . ISBN 9780821802397 .

[Garcia-Diaz_2017-9] Jump up to: ^а ^б ^с Гарсиа-Диас, Хесус; Санчес-Эрнандес, Хаиро; Менчака-Мендес, Рикардо; Менчака-Мендес, Роландо (01 июля 2017 г.). «Когда худший коэффициент аппроксимации дает лучшую производительность: алгоритм с 3 приближениями для задачи вершины k -центра». Журнал эвристики . 23 (5): 349–366. дои : 10.1007/s10732-017-9345-x . ISSN 1381-1231 . S2CID 254500532 .

[10] Фельдманн, Андреас Эмиль (01 марта 2019 г.). «Аппроксимации с фиксированными параметрами для задач k-центра в графах шоссе малой размерности» . Алгоритмика . 81 (3): 1031–1052. arXiv : 1605.02530 . дои : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .

[11] Федер, Томас; Грин, Дэниел (1 января 1988 г.). «Оптимальные алгоритмы приближенной кластеризации» . Материалы двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. дои : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 . S2CID 658151 .

[12] Фельдманн, Андреас Эмиль; Маркс, Даниэль (01 июля 2020 г.). «Параметризованная жесткость задачи k-центра в транспортных сетях» . Алгоритмика . 82 (7): 1989–2005. arXiv : 1802.08563 . дои : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .

[13] Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $$k$$-центр: различие удвоения и измерения шоссе» . В Бекосе, Майкл А.; Кауфманн, Майкл (ред.). Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 13453. Чам: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . дои : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .

[14] Бизли, Дж. Э. (1990). «ИЛИ-библиотека: Распространение тестовых задач по электронной почте». Журнал Общества операционных исследований . 41 (11): 1069–1072. дои : 10.2307/2582903 . JSTOR 2582903 .

[15] Рейнельт, Герхард (ноябрь 1991 г.). «TSPLIB — Библиотека задач коммивояжера». Журнал ORSA по вычислительной технике . 3 (4): 376–384. дои : 10.1287/ijoc.3.4.376 . ISSN 0899-1499 .

[16] Рана, Ротанг; Гарг, Дипак (март 2009 г.). «Эвристические подходы к проблеме К-центра». 2009 Международная конференция по передовым вычислениям IEEE . IEEE. стр. 332–335. дои : 10.1109/iadcc.2009.4809031 . ISBN 9781424429271 . S2CID 12453616 .

[17] Мигелич, Юрий; Робич, Борут (2005). «Эффективное решение проблемы k -центра с помощью алгоритма доминирующего множества» . Журнал вычислительной техники и информационных технологий . 13 (3): 225. doi : 10.2498/cit.2005.03.05 . ISSN 1330-1136 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]