Размер шоссе

Измерение шоссе — это параметр графа , моделирующий транспортные сети , такие как дорожные сети или общественного транспорта сети . Впервые он был формально определен Авраамом и др. ^[1] на основе наблюдения Bast et al. ^[2]^[3] что любая дорожная сеть имеет редкий набор «транзитных узлов», так что движение из точки A в достаточно удаленную точку B по кратчайшему маршруту всегда будет проходить через один из этих транзитных узлов. Также было предложено, чтобы размер шоссе хорошо отражал свойства сетей общественного транспорта (по крайней мере, в соответствии с определениями 1 и 2 ниже), учитывая, что более длинные маршруты с использованием автобусов , поездов или самолетов обычно обслуживаются более крупными транзитными узлами (станциями). и аэропорты). Это относится к парадигме распределения «звезда-концентратор» в оптимизации транспортной топологии.

Определения

Существует несколько определений измерения шоссе. ^[4] Каждое определение измерения шоссе использует набор попаданий из определенного набора кратчайших путей : с учетом графа $G=(V,E)$ с длиной кромки $\ell :E\to \mathbb {R} ^{+}$ , позволять ${\mathcal {P}}$ содержать каждый набор вершин $P\subseteq V$ такой, что $P$ индуцирует кратчайший путь между некоторой парой вершин $G$ , в зависимости от длины ребра $\ell$ . Чтобы измерить размер шоссе, мы определяем «редкость» набора попаданий подмножества ${\mathcal {P}}$ в локальной области графа, для которой определим шар радиуса $r>0$ вокруг вершины $u\in V$ быть набором $B_{r}(u)\subseteq V$ вершин на расстоянии не более $r$ от $u$ в $G$ в зависимости от длины кромки $\ell$ . В контексте графов с низкой размерностью шоссе вершины множества совпадений для кратчайших путей называются концентраторами .

Определение 1

Исходное определение ^[1] Размер шоссе измеряет разреженность комплекта ступиц $H$ кратчайших путей, содержащихся в шаре радиуса $4r$ :

Размер шоссе $G$ это наименьшее целое число $h_{1}$ такая, что для любого радиуса $r>0$ и любой узел $u\in V$ есть ударный набор $H\subseteq B_{4r}(u)$ размера максимум $h_{1}$ для всех кратчайших путей $P\in {\mathcal {P}}$ длиной более $r$ для чего $P\subseteq B_{4r}(u)$ .

В варианте этого определения используются шары радиуса $cr$ для некоторой константы $c>4$ . Выбор константы больше 4 подразумевает дополнительные структурные свойства графов ограниченной размерности шоссе, которые можно использовать алгоритмически. ^[5]

Определение 2

Последующее определение ^[6] Размер шоссе измеряет разреженность комплекта ступиц $H$ кратчайших путей, пересекающих шар радиуса $2r$ :

Размер шоссе $G$ это наименьшее целое число $h_{2}$ такая, что для любого радиуса $r>0$ и любой узел $u\in V$ есть ударный набор $H\subseteq V$ размера максимум $h_{2}$ для всех кратчайших путей $P\in {\mathcal {P}}$ длиной более $r$ и самое большее $2r$ для чего $P\cap B_{2r}(u)\neq \emptyset$ .

Это определение слабее первого, т. е. каждый график размерности шоссе $h_{1}$ также имеет размер шоссе $h_{2}$ , но не наоборот. ^[5]

Определение 3

По третьему определению ^[7] размера шоссе вводится понятие «тропа свидетеля»: для заданного радиуса $r$ , кратчайший путь $P\in {\mathcal {P}}$ имеет $r$ - путь свидетеля $Q\in {\mathcal {P}}$ если $Q$ имеет длину более $r$ и $Q$ можно получить из $P$ добавив не более одной вершины к любому концу $P$ (т.е. $Q$ имеет не более чем на 2 вершины больше, чем $P$ и эти дополнительные вершины инцидентны $P$ ). Обратите внимание, что $P$ может быть короче, чем $r$ но содержится в $Q$ , длина которого больше $r$ .

Размер шоссе $G$ это наименьшее целое число $h_{3}$ такая, что для любого радиуса $r>0$ и любой узел $u\in V$ есть ударный набор $H\subseteq V$ размера максимум $h_{3}$ для всех кратчайших путей $P\in {\mathcal {P}}$ которые имеют $r$ - путь свидетеля $Q$ с $Q\cap B_{2r}(u)\neq \emptyset$ .

Это определение является более сильным, чем приведенное выше, т. е. каждый график размеров шоссе $h_{1}$ также имеет размер шоссе $h_{3}=O(h_{1}^{2})$ , но $h_{1}$ не может быть ограничено с точки зрения $h_{3}$ . ^[5]

Обложка кратчайшего пути

С измерением шоссе тесно связано понятие кратчайшего пути. ^[1] где порядок кванторов в определении обратный, т. е. вместо набора узлов для каждого шара имеется один набор узлов. $H$ , которая разрежена в каждом шаре:

Учитывая радиус $r>0$ , $r$ - кратчайший путь покрытия $G$ это потрясающий набор $H\subseteq V$ для всех кратчайших путей в ${\mathcal {P}}$ длиной более $r$ и самое большее $2r$ . $r$ - покрытие кратчайшего пути $H$ локально  $h$ -разреженный, если есть узел $u\in V$ мяч $B_{2r}(u)$ содержит не более $h$ вершины $H$ , то есть, $|B_{2r}(u)\cap H|\leq h$ .

Каждый граф ограниченной размерности шоссе $h$ (согласно любому из приведенных определений) также имеет локально $h$ -редкий $r$ - кратчайший путь для каждого $r>0$ , но не наоборот. ^[4] Для алгоритмических целей часто удобнее работать с одним набором попаданий для каждого радиуса. $r$ , что делает покрытие кратчайшего пути важным инструментом для алгоритмов на графах ограниченной размерности шоссе.

Связь с другими параметрами графика

Размерность шоссе сочетает в себе структурные и метрические свойства графов и, таким образом, несопоставима с обычными структурными и метрическими параметрами. В частности, для любого графа можно выбрать такие длины ребер, чтобы размер шоссе был равен $1$ , ^[5] в то же время некоторые графы с очень простой структурой, такие как деревья, могут иметь произвольно большую размерность шоссе. Это означает, что параметр размерности шоссе несравним с параметрами структурного графа, такими как ширина дерева , ширина клика или минорная свобода . С другой стороны, звезда с единичной длиной ребра имеет размерность шоссе. $1$ (согласно определениям 1 и 2 выше), но неограниченная удвоенная размерность , а $k\times k$ граф сетки с единичными длинами ребер имеет постоянное удвоенное измерение , но размерность шоссе $\Omega (k)$ . ^[1] Это значит, что размер магистрали по определениям 1 и 2 также несравним с удвоенным размером . Любой граф ограниченной размерности шоссе согласно определению 3 выше также имеет ограниченную удвоенную размерность. ^[7]

Вычисление размеров шоссе

Вычисление размера шоссе данного графа является NP-трудным . ^[5] Предполагая, что все кратчайшие пути уникальны (что можно сделать, слегка изменив длины ребер), $O(\log h)$ - аппроксимация может быть вычислена за полиномиальное время, ^[6] учитывая, что размерность графа по шоссе равна $h$ . Неизвестно, можно ли вычислить размеры шоссе с фиксированными параметрами (FPT), однако есть результаты по твердости, указывающие на то, что это, скорее всего, не так. ^[8] В частности, эти результаты подразумевают, что при стандартных предположениях о сложности алгоритм FPT не может ни вычислить размеры шоссе снизу вверх (от наименьшего значения $r$ до наибольшего), ни сверху вниз (от наибольшего значения $r$ до самого маленького).

Алгоритмы, использующие измерение шоссе

Алгоритмы кратчайшего пути

Можно формально доказать, что некоторые эвристики для вычисления кратчайших путей, такие как алгоритмы «Охват», «Иерархии сжатия» , «Транзитные узлы» и «Маркировка узлов» , работают быстрее, чем другие алгоритмы поиска кратчайшего пути (например, алгоритм Дейкстры ) на графах ограниченной размерности шоссе в соответствии с определением 3. выше. ^[7]

Приближения для NP-трудных задач

Важнейшее свойство, которое можно использовать алгоритмически для графов ограниченной размерности шоссе, заключается в том, что вершины, находящиеся далеко от узлов покрытия кратчайшего пути, группируются в так называемые города: ^[5]

Учитывая радиус $r>0$ , $r$ - покрытие кратчайшего пути $H$ из $G$ и вершина $u\in V$ на расстоянии более $2r$ от $H$ , набор $T\subseteq V$ вершин на расстоянии не более $r$ от $u$ в зависимости от длины кромки $\ell$ называется городом . Совокупность всех вершин, не лежащих ни в одном городе, называется разрастанием .

Можно показать, что диаметр каждого города не более $r$ , а расстояние между городом и любой вершиной вне его больше, чем $r$ . Более того, расстояние от любой вершины разрастания до какого-либо узла $H$ самое большее $2r$ .

Основываясь на этой структуре, Feldmann et al. ^[5] определил декомпозицию городов , которая рекурсивно разлагает разрастание на города с экспоненциально растущими значениями. $r$ . Для графа ограниченной размерности шоссе (согласно определению 1 выше) это разложение можно использовать для нахождения вложения метрики в граф ограниченной ширины дерева , который сколь угодно хорошо сохраняет расстояния между вершинами. Благодаря этому вложению можно получить квазиполиномиального времени схемы аппроксимации (QPTAS) для различных задач, таких как коммивояжёр (TSP), дерево Штейнера , k-медиана и расположение объекта. ^[5]

Для задач кластеризации, таких как k-медиана, k-средние и расположение объекта, более быстрые схемы аппроксимации с полиномиальным временем (PTAS) для графиков ограниченного размера шоссе в соответствии с определением 1 выше. известны ^[9] Для задач проектирования сети, таких как TSP и Дерево Штейнера, неизвестно, как получить PTAS.

Для задачи k-центра неизвестно, существует ли PTAS для графов ограниченной размерности шоссе, однако вычислить a ( $2-\varepsilon$ )- аппроксимация на графиках размерности магистралей $O(\log ^{2}{n})$ , ^[10] что означает, что любой ( $2-\varepsilon$ Алгоритм )-аппроксимации требует как минимум двойного экспоненциального времени в измерении шоссе, если только P = NP. ^[10] С другой стороны, было показано, что параметризованный $3/2$ -алгоритм аппроксимации со временем выполнения $2^{O(kh\log {h})}n^{O(1)}$ существует для k-центра , где $h$ — размер шоссе согласно любому из приведенных выше определений. ^[10] Известно , что при использовании определения 1 выше параметризованная схема аппроксимации (PAS). существует $k$ и $h$ в качестве параметров. ^[11]

Для задачи емкостного k-центра не существует PAS , параметризованного $k$ и размер шоссе $h$ , если только FPT=W[1] . ^[12] Это примечательно, поскольку обычно (т. е. для всех упомянутых выше задач) если существует схема аппроксимации для метрик малой размерности удвоения , то существует и схема аппроксимации для графиков ограниченной размерности шоссе. Но для емкостного k-центра существует PAS , параметризованный $k$ и удвоенное измерение . ^[12]

Внешние ссылки

Видео на тему « Мощный k-центр в режиме низкого удвоения и шоссе » ^[12] предоставлено Тунг Ан Ву, 2022 г.
Видео « Алгоритмы решения сложных задач на графах малой размерности шоссе », предоставленное Андреасом Эмилем Фельдманном в ICERM, Университет Брауна, Провиденс, США, май 2019 г.
Видео по теме « (1 + ε)-вложение графов размерности малых автомагистралей в графы ограниченной древовидной ширины » ^[5] предоставлено Андреасом Эмилем Фельдманном в Институте Хаусдорфа, Бонн, Германия, 2015 г.
Видео на тему « Измерение шоссе: от практики к теории и обратно » ^[6] предоставлено Эндрю Голдбергом

Ссылки

^ Jump up to: ^а ^б ^с ^д Авраам, Иттай; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. (17 января 2010 г.). Размерность шоссе, кратчайшие пути и доказуемо эффективные алгоритмы . Общество промышленной и прикладной математики. стр. 782–793. дои : 10.1137/1.9781611973075.64 . ISBN 978-0-89871-701-3 . S2CID 9330775 .
^ Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Сандерс, Питер; Шультес, Доминик (6 января 2007 г.), Эпплгейт, Дэвид; Столтинг Бродал, Герт (ред.), «На пути к запросам кратчайшего пути в постоянном времени в дорожных сетях», 2007 г., Материалы девятого семинара по разработке алгоритмов и экспериментам (ALENEX) , Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, стр. 46–59, номер документа : 10.1137/1.9781611972870.5 , ISBN. 978-1-61197-287-0
^ Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Деметреску, Камил; Гольдберг, Эндрю; Джонсон, Дэвид (2006). «ТРАНЗИТ: сверхбыстрые запросы кратчайшего пути с предварительной обработкой за линейное время» . Задача о кратчайшем пути: девятая задача по внедрению DIMACS .
^ Jump up to: ^а ^б Блюм, Йоханнес (2019). «Иерархия параметров транспортной сети и результатов твердости» . Материалы 14-го Международного симпозиума по параметризованным и точным вычислениям (IPEC 2019) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.IPEC.2019.4 . S2CID 166228480 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Фельдманн, Андреас Эмиль; Фунг, Вай Шинг; Кенеманн, Йохен; Пост, Ян (январь 2018 г.). «$(1+\varepsilon)$-вложение графов малой размерности шоссе в графы ограниченной древовидной ширины» . SIAM Journal по вычислительной технике . 47 (4): 1667–1704. arXiv : 1502.04588 . дои : 10.1137/16M1067196 . ISSN 0097-5397 . S2CID 11339698 .
^ Jump up to: ^а ^б ^с Авраам, Иттай; Деллинг, Дэниел; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. (2011). «Алгоритмы измерения VC и кратчайшего пути» . В Ачето, Лука; Хенцингер, Моника; Сгалл, Иржи (ред.). Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 6755. Берлин, Гейдельберг: Springer. стр. 690–699. дои : 10.1007/978-3-642-22006-7_58 . ISBN 978-3-642-22006-7 .
^ Jump up to: ^а ^б ^с Авраам, Иттай; Деллинг, Дэниел; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. (08 декабря 2016 г.). «Размеры шоссе и доказуемо эффективные алгоритмы кратчайшего пути» . Журнал АКМ . 63 (5): 41:1–41:26. дои : 10.1145/2985473 . ISSN 0004-5411 . S2CID 1943037 .
^ Блюм, Йоханнес; Диссер, Янн; Фельдманн, Андреас Эмиль; Гупта, Сиддхартх; Зых-Павлевич, Анна (2022). «О разреженных наборах ударов: от справедливого покрытия вершин до измерения шоссе» . Материалы 17-го Международного симпозиума по параметризованным и точным вычислениям (IPEC 2022) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.IPEC.2022.5 .
^ Фельдманн, Андреас Эмиль; Саулпик, Дэвид (01 декабря 2021 г.). «Схемы аппроксимации полиномиального времени для кластеризации в графах шоссе малой размерности» . Журнал компьютерных и системных наук . 122 : 72–93. дои : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 .
^ Jump up to: ^а ^б ^с Фельдманн, Андреас Эмиль (01 марта 2019 г.). «Аппроксимации с фиксированными параметрами для задач k-центра в графах шоссе малой размерности» . Алгоритмика . 81 (3): 1031–1052. arXiv : 1605.02530 . дои : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 .
^ Беккер, Амария; Кляйн, Филип Н.; Саулпик, Дэвид (2018). «Схемы аппроксимации полиномиального времени для маршрутизации k-центра, k-медианы и емкостного транспортного средства в ограниченном измерении шоссе» . Материалы 26-го ежегодного европейского симпозиума по алгоритмам (ESA 2018) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.ESA.2018.8 .
^ Jump up to: ^а ^б ^с Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $k$ -центр: различие удвоения и измерения шоссе» . В Бекосе, Майкл А.; Кауфманн, Майкл (ред.). Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Чам: Международное издательство Springer. стр. 215–229. arXiv : 2209.00675 . дои : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .

[:0-1] Jump up to: ^а ^б ^с ^д Авраам, Иттай; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. (17 января 2010 г.). Размерность шоссе, кратчайшие пути и доказуемо эффективные алгоритмы . Общество промышленной и прикладной математики. стр. 782–793. дои : 10.1137/1.9781611973075.64 . ISBN 978-0-89871-701-3 . S2CID 9330775 .

[2] Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Сандерс, Питер; Шультес, Доминик (6 января 2007 г.), Эпплгейт, Дэвид; Столтинг Бродал, Герт (ред.), «На пути к запросам кратчайшего пути в постоянном времени в дорожных сетях», 2007 г., Материалы девятого семинара по разработке алгоритмов и экспериментам (ALENEX) , Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, стр. 46–59, номер документа : 10.1137/1.9781611972870.5 , ISBN. 978-1-61197-287-0

[3] Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Деметреску, Камил; Гольдберг, Эндрю; Джонсон, Дэвид (2006). «ТРАНЗИТ: сверхбыстрые запросы кратчайшего пути с предварительной обработкой за линейное время» . Задача о кратчайшем пути: девятая задача по внедрению DIMACS .

[:1-4] Jump up to: ^а ^б Блюм, Йоханнес (2019). «Иерархия параметров транспортной сети и результатов твердости» . Материалы 14-го Международного симпозиума по параметризованным и точным вычислениям (IPEC 2019) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.IPEC.2019.4 . S2CID 166228480 .

[:2-5] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Фельдманн, Андреас Эмиль; Фунг, Вай Шинг; Кенеманн, Йохен; Пост, Ян (январь 2018 г.). «$(1+\varepsilon)$-вложение графов малой размерности шоссе в графы ограниченной древовидной ширины» . SIAM Journal по вычислительной технике . 47 (4): 1667–1704. arXiv : 1502.04588 . дои : 10.1137/16M1067196 . ISSN 0097-5397 . S2CID 11339698 .

[:3-6] Jump up to: ^а ^б ^с Авраам, Иттай; Деллинг, Дэниел; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. (2011). «Алгоритмы измерения VC и кратчайшего пути» . В Ачето, Лука; Хенцингер, Моника; Сгалл, Иржи (ред.). Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 6755. Берлин, Гейдельберг: Springer. стр. 690–699. дои : 10.1007/978-3-642-22006-7_58 . ISBN 978-3-642-22006-7 .

[:4-7] Jump up to: ^а ^б ^с Авраам, Иттай; Деллинг, Дэниел; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. (08 декабря 2016 г.). «Размеры шоссе и доказуемо эффективные алгоритмы кратчайшего пути» . Журнал АКМ . 63 (5): 41:1–41:26. дои : 10.1145/2985473 . ISSN 0004-5411 . S2CID 1943037 .

[8] Блюм, Йоханнес; Диссер, Янн; Фельдманн, Андреас Эмиль; Гупта, Сиддхартх; Зых-Павлевич, Анна (2022). «О разреженных наборах ударов: от справедливого покрытия вершин до измерения шоссе» . Материалы 17-го Международного симпозиума по параметризованным и точным вычислениям (IPEC 2022) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.IPEC.2022.5 .

[9] Фельдманн, Андреас Эмиль; Саулпик, Дэвид (01 декабря 2021 г.). «Схемы аппроксимации полиномиального времени для кластеризации в графах шоссе малой размерности» . Журнал компьютерных и системных наук . 122 : 72–93. дои : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 .

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

[11] Беккер, Амария; Кляйн, Филип Н.; Саулпик, Дэвид (2018). «Схемы аппроксимации полиномиального времени для маршрутизации k-центра, k-медианы и емкостного транспортного средства в ограниченном измерении шоссе» . Материалы 26-го ежегодного европейского симпозиума по алгоритмам (ESA 2018) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.ESA.2018.8 .

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]