Размеры шоссе

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

Кратчайший путь покрытия

Понятие, тесно связанное с измерением шоссе, — это понятие покрытия кратчайшего пути ^[1] , где порядок квантификаторов в определении обратный, т. е. вместо набора концентраторов для каждого шара, есть один набор концентраторов , который является разреженным в каждом шаре: ${\displaystyle H}$

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

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

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

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

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

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

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

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

Можно формально доказать, что некоторые эвристики для вычисления кратчайших путей, такие как алгоритмы Reach, Contraction Hierarchies , Transit Nodes и Hub Labeling , работают быстрее, чем другие алгоритмы кратчайшего пути (например, алгоритм Дейкстры ) на графах ограниченной размерности шоссе в соответствии с определением 3 выше. ^[7]

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

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

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

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

На основе этой структуры Фельдман и др. ^[5] определили разложение городов , которое рекурсивно разлагает разрастание на города экспоненциально растущих значений . Для графа ограниченной размерности шоссе (согласно определению 1 выше) это разложение можно использовать для нахождения метрического вложения в граф ограниченной ширины дерева , которое сохраняет расстояния между вершинами произвольно хорошо. Благодаря этому вложению можно получить квазиполиномиальные схемы аппроксимации времени (QPTAS) для различных задач, таких как коммивояжер (TSP), дерево Штейнера , k-медиана и местоположение предприятия. ^[5] ${\displaystyle r}$

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

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

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

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

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

Ссылки

1. Авраам, Иттай; Фиат, Амос; Голдберг, Эндрю В.; Вернек, Ренато Ф. (2010-01-17). Измерение шоссе, кратчайшие пути и доказуемо эффективные алгоритмы. Общество промышленной и прикладной математики. стр. 782–793. doi :10.1137/1.9781611973075.64. ISBN 978-0-89871-701-3. S2CID  9330775.
2. Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Сандерс, Питер; Шультес, Доминик (2007-01-06), Эпплгейт, Дэвид; Столтинг Бродал, Герт (ред.), «Переход к запросам на кратчайший путь за постоянное время в дорожных сетях», 2007 Труды Девятого семинара по разработке алгоритмов и экспериментам (ALENEX) , Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, стр. 46–59, doi : 10.1137/1.9781611972870.5 , ISBN 978-1-61197-287-0
3. Баст, Хольгер; Функе, Стефан; Матиевич, Домагой; Деметреску, Камил; Голдберг, Эндрю; Джонсон, Дэвид (2006). "TRANSIT: Сверхбыстрые запросы на кратчайший путь с предварительной обработкой за линейное время". Задача о кратчайшем пути: девятая задача по реализации DIMACS .
4. Блюм, Йоханнес (2019). «Иерархия параметров транспортной сети и результатов твердости». Материалы 14-го Международного симпозиума по параметризованным и точным вычислениям (IPEC 2019) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.IPEC.2019.4 . S2CID  166228480.
5. Фельдманн, Андреас Эмиль; Фунг, Вай Шинг; Кёнеманн, Йохен; Пост, Ян (январь 2018 г.). «Вложение графов малой размерности магистралей в графы ограниченной древовидной ширины ($(1+\varepsilon)$)». Журнал SIAM по вычислениям . 47 (4): 1667–1704. arXiv : 1502.04588 . doi : 10.1137/16M1067196. ISSN  0097-5397. S2CID  11339698.
6. Abraham, Ittai; Delling, Daniel; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. (2011). "VC-Dimension and Shortest Path Algorithms". В Aceto, Luca; Henzinger, Monika; Sgall, Jiří (ред.). Automata, Languages ​​and Programming . Lecture Notes in Computer Science. Vol. 6755. Berlin, Heidelberg: Springer. pp. 690–699. doi :10.1007/978-3-642-22006-7_58. ISBN 978-3-642-22006-7.
7. Abraham, Ittai; Delling, Daniel; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. (2016-12-08). «Highway Dimension and Provably Efficient Shortest Path Algorithms». Journal of the ACM . 63 (5): 41:1–41:26. doi :10.1145/2985473. ISSN  0004-5411. S2CID  1943037.
8. Блюм, Йоханнес; Диссер, Янн; Фельдманн, Андреас Эмиль; Гупта, Сиддхартх; Зых-Павлевич, Анна (2022). «О разреженных наборах ударов: от справедливого покрытия вершин до измерения шоссе». Материалы 17-го Международного симпозиума по параметризованным и точным вычислениям (IPEC 2022) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.IPEC.2022.5 .
9. Фельдманн, Андреас Эмиль; Саульпик, Дэвид (2021-12-01). «Схемы аппроксимации полиномиального времени для кластеризации в графах малой размерности магистралей». Журнал компьютерных и системных наук . 122 : 72–93. doi :10.1016/j.jcss.2021.06.002. ISSN  0022-0000.
10. Фельдманн, Андреас Эмиль (2019-03-01). "Аппроксимации с фиксированными параметрами для задач k-центра в графах малой размерности шоссе". Algorithmica . 81 (3): 1031–1052. arXiv : 1605.02530 . doi :10.1007/s00453-018-0455-0. ISSN  1432-0541.
11. Беккер, Амария; Кляйн, Филип Н.; Саулпик, Дэвид (2018). «Схемы аппроксимации полиномиального времени для маршрутизации k-центра, k-медианы и емкостного транспортного средства в ограниченном измерении шоссе». Материалы 26-го ежегодного европейского симпозиума по алгоритмам (ESA 2018) . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.ESA.2018.8 .
12. Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный k-центр: различение удвоения и размерности шоссе». В Bekos, Michael A.; Кауфманн, Майкл (ред.). Графовые концепции в информатике . Конспект лекций по информатике. Cham: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . doi :10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.