Dimensión de la carretera

La dimensión de autopista es un parámetro gráfico que modela redes de transporte , como redes de carreteras o redes de transporte público . Fue definida formalmente por primera vez por Abraham et al. ^[1] basándose en la observación de Bast et al. ^{[2] [3]} de que cualquier red de carreteras tiene un conjunto disperso de "nodos de tránsito", de modo que conducir desde un punto A hasta un punto B suficientemente alejado a lo largo de la ruta más corta siempre pasará por uno de estos nodos de tránsito. También se ha propuesto que la dimensión de autopista captura bien las propiedades de las redes de transporte público (al menos de acuerdo con las definiciones 1 y 2 a continuación), dado que las rutas más largas que utilizan autobuses , trenes o aviones normalmente serán atendidas por centros de tránsito más grandes (estaciones y aeropuertos). Esto se relaciona con el paradigma de distribución de radios-centros en la optimización de la topología de transporte.

Existen varias definiciones de la dimensión de la autopista. ^[4] Cada definición de la dimensión de la autopista utiliza un conjunto de impacto de un cierto conjunto de caminos más cortos : dado un grafo con longitudes de arista , sea que contenga cada conjunto de vértices tal que induce un camino más corto entre algún par de vértices de , de acuerdo con las longitudes de arista . Para medir la dimensión de la autopista, determinamos la "escasez" de un conjunto de impacto de un subconjunto de en un área local del grafo, para lo cual definimos una bola de radio alrededor de un vértice como el conjunto de vértices a una distancia máxima de en de acuerdo con las longitudes de arista . En el contexto de grafos de baja dimensión de la autopista, los vértices de un conjunto de impacto para los caminos más cortos se denominan ejes . ${\displaystyle G=(V,E)}$${\displaystyle \ell :E\to \mathbb {R} ^{+}}$${\displaystyle {\mathcal {P}}}$${\displaystyle P\subseteq V}$${\estilo de visualización P}$${\estilo de visualización G}$${\displaystyle \ell}$${\displaystyle {\mathcal {P}}}$${\displaystyle r>0}$${\displaystyle u\en V}$${\displaystyle B_{r}(u)\subseteq V}$${\estilo de visualización r}$${\estilo de visualización u}$${\estilo de visualización G}$${\displaystyle \ell}$

La definición original ^[1] de la dimensión de la carretera mide la escasez de un conjunto central de caminos más cortos contenidos dentro de una bola de radio :${\estilo de visualización H}$${\estilo de visualización 4r}$

La dimensión de la carretera de es el entero más pequeño tal que para cualquier radio y cualquier nodo hay un conjunto impactante de tamaño como máximo para todas las rutas más cortas de longitud mayor que para las cuales .${\estilo de visualización G}$$estilo de visualización h_{1}}$${\displaystyle r>0}$${\displaystyle u\en V}$ ${\displaystyle H\subseteq B_{4r}(u)}$$estilo de visualización h_{1}}$${\displaystyle P\in {\mathcal {P}}}$${\estilo de visualización r}$${\displaystyle P\subseteq B_{4r}(u)}$

Una variante de esta definición utiliza bolas de radio para una constante . Elegir una constante mayor que 4 implica propiedades estructurales adicionales de los grafos de dimensión de autopista acotada, que pueden explotarse algorítmicamente. ^[5]${\estilo de visualización cr}$${\displaystyle c>4}$

Una definición posterior ^[6] de la dimensión de la carretera mide la escasez de un conjunto central de caminos más cortos que intersecan una bola de radio :${\estilo de visualización H}$${\estilo de visualización 2r}$

La dimensión de la carretera de es el entero más pequeño tal que para cualquier radio y cualquier nodo existe un conjunto impactante de tamaño como máximo para todas las rutas más cortas de longitud mayor que y como máximo para las cuales .${\estilo de visualización G}$$estilo de visualización h_{2}$${\displaystyle r>0}$${\displaystyle u\en V}$ ${\displaystyle H\subseteq V}$$estilo de visualización h_{2}$${\displaystyle P\in {\mathcal {P}}}$${\estilo de visualización r}$${\estilo de visualización 2r}$${\displaystyle P\cap B_{2r}(u)\neq \conjunto vacío}$

Esta definición es más débil que la primera, es decir, todo gráfico de dimensión de autopista también tiene dimensión de autopista , pero no al revés. ^[5]$estilo de visualización h_{1}}$$estilo de visualización h_{2}$

Para la tercera definición ^[7] de la dimensión de la autopista introducimos la noción de un "camino testigo": para un radio dado , un camino más corto tiene un camino testigo si tiene una longitud mayor que y se puede obtener de añadiendo como máximo un vértice a cada extremo de (es decir, tiene como máximo 2 vértices más que y estos vértices adicionales son incidentes a ). Nótese que puede ser más corto que pero está contenido en , que tiene una longitud mayor que .${\estilo de visualización r}$${\displaystyle P\in {\mathcal {P}}}$${\estilo de visualización r}$ ${\displaystyle Q\in {\mathcal {P}}}$${\estilo de visualización Q}$${\estilo de visualización r}$${\estilo de visualización Q}$${\estilo de visualización P}$${\estilo de visualización P}$${\estilo de visualización Q}$${\estilo de visualización P}$${\estilo de visualización P}$${\estilo de visualización P}$${\estilo de visualización r}$${\estilo de visualización Q}$${\estilo de visualización r}$

La dimensión de la carretera de es el entero más pequeño tal que para cualquier radio y cualquier nodo existe un conjunto de impacto de tamaño como máximo para todas las rutas más cortas que tienen una ruta testigo con .${\estilo de visualización G}$$estilo de visualización h_{3}$${\displaystyle r>0}$${\displaystyle u\en V}$ ${\displaystyle H\subseteq V}$$estilo de visualización h_{3}$${\displaystyle P\in {\mathcal {P}}}$${\estilo de visualización r}$${\estilo de visualización Q}$${\displaystyle Q\cap B_{2r}(u)\neq \conjunto vacío}$

Esta definición es más fuerte que la anterior, es decir, cada gráfico de dimensión de autopista también tiene dimensión de autopista , pero no puede estar acotado en términos de . ^[5]$estilo de visualización h_{1}}$$estilo de visualización h_{3}=O(h_{1}^{2})}$$estilo de visualización h_{1}}$$estilo de visualización h_{3}$

Una noción estrechamente relacionada con la dimensión de la carretera es la de cobertura del camino más corto, ^[1] donde el orden de los cuantificadores en la definición se invierte, es decir, en lugar de un conjunto de ejes para cada bola, hay un conjunto de ejes , que es disperso en cada bola:${\estilo de visualización H}$

Dado un radio , una cobertura de ruta más corta de es un conjunto de impacto para todas las rutas más cortas en de longitud mayor que y como máximo . La cobertura de ruta más corta es localmente escasa si cualquier nodo de la bola contiene como máximo vértices de , es decir, .${\displaystyle r>0}$${\estilo de visualización r}$${\estilo de visualización G}$ ${\displaystyle H\subseteq V}$${\displaystyle {\mathcal {P}}}$${\estilo de visualización r}$${\estilo de visualización 2r}$${\estilo de visualización r}$${\estilo de visualización H}$${\estilo de visualización h}$${\displaystyle u\en V}$$Estilo de visualización B2r(u)$${\estilo de visualización h}$${\estilo de visualización H}$${\displaystyle |B_{2r}(u)\cap H|\leq h}$

Cada gráfico de dimensión de autopista acotada (según cualquiera de las definiciones anteriores) también tiene una cobertura de ruta más corta localmente dispersa para cada , pero no al revés. ^[4] Para fines algorítmicos, a menudo es más conveniente trabajar con un conjunto de impactos para cada radio , lo que hace que las coberturas de ruta más corta sean una herramienta importante para los algoritmos en gráficos de dimensión de autopista acotada. ${\estilo de visualización h}$${\estilo de visualización h}$${\estilo de visualización r}$${\displaystyle r>0}$${\estilo de visualización r}$

La dimensión de autopista combina propiedades estructurales y métricas de los grafos, y por lo tanto es incomparable a los parámetros estructurales y métricos comunes. En particular, para cualquier grafo es posible elegir longitudes de aristas tales que la dimensión de autopista sea , ^[5] mientras que al mismo tiempo algunos grafos con estructura muy simple como los árboles pueden tener una dimensión de autopista arbitrariamente grande. Esto implica que el parámetro de dimensión de autopista es incomparable a los parámetros de grafo estructural como treewidth , cliquewidth o minor-freeness . Por otro lado, una estrella con longitudes de aristas unitarias tiene dimensión de autopista (según las definiciones 1 y 2 anteriores) pero dimensión de duplicación ilimitada , mientras que un grafo de cuadrícula con longitudes de aristas unitarias tiene dimensión de duplicación constante pero dimensión de autopista . ^[1] Esto significa que la dimensión de autopista según las definiciones 1 y 2 también es incomparable a la dimensión de duplicación . Cualquier grafo de dimensión de autopista acotada según la definición 3 anterior, también tiene dimensión de duplicación acotada. ^[7]${\estilo de visualización 1}$${\estilo de visualización 1}$${\displaystyle k\veces k}$ ${\displaystyle \Omega(k)}$

Calcular la dimensión de la autopista de un grafo dado es NP-hard . ^[5] Suponiendo que todos los caminos más cortos son únicos (lo que se puede hacer perturbando ligeramente las longitudes de los bordes), se puede calcular una aproximación en tiempo polinomial, [ 6 ^] dado que la dimensión de la autopista del grafo es . No se sabe si el cálculo de la dimensión de la autopista es manejable con parámetros fijos (FPT), sin embargo, hay resultados de dureza que indican que probablemente este no sea el caso. ^[8] En particular, estos resultados implican que, bajo supuestos de complejidad estándar , un algoritmo FPT no puede calcular la dimensión de la autopista de abajo hacia arriba (desde el valor más pequeño al más grande) ni de arriba hacia abajo (desde el valor más grande al más pequeño). ${\displaystyle O(\log h)}$${\estilo de visualización h}$${\estilo de visualización r}$${\estilo de visualización r}$

Se puede demostrar formalmente que algunas heurísticas para calcular rutas más cortas, como los algoritmos Reach, Contraction Hierarchies , Transit Nodes y Hub Labelling , se ejecutan más rápido que otros algoritmos de ruta más corta (por ejemplo, el algoritmo de Dijkstra ) en gráficos de dimensión de autopista acotada de acuerdo con la definición 3 anterior. ^[7]

Una propiedad crucial que se puede explotar algorítmicamente para gráficos de dimensión de autopista acotada es que los vértices que están lejos de los centros de una ruta más corta se agrupan en las denominadas ciudades: ^[5]

Dado un radio , una ruta de cobertura más corta de , y un vértice a una distancia mayor que de , el conjunto de vértices a una distancia máxima de de acuerdo con las longitudes de las aristas se denomina ciudad . El conjunto de todos los vértices que no se encuentran en ninguna ciudad se denomina expansión .${\displaystyle r>0}$${\estilo de visualización r}$${\estilo de visualización H}$${\estilo de visualización G}$${\displaystyle u\en V}$${\estilo de visualización 2r}$${\estilo de visualización H}$${\displaystyle T\subseteq V}$${\estilo de visualización r}$${\estilo de visualización u}$${\displaystyle \ell}$

Se puede demostrar que el diámetro de cada ciudad es como máximo , mientras que la distancia entre una ciudad y cualquier vértice fuera de ella es mayor que . Además, la distancia desde cualquier vértice en la expansión a algún centro de es como máximo . ${\estilo de visualización r}$${\estilo de visualización r}$${\estilo de visualización H}$${\estilo de visualización 2r}$

Basándose en esta estructura, Feldmann et al. ^[5] definieron la descomposición de ciudades , que descompone recursivamente la expansión urbana en ciudades con valores de crecimiento exponencial . Para un gráfico de dimensión de autopista acotada (según la definición 1 anterior), esta descomposición se puede utilizar para encontrar una incrustación métrica en un gráfico de ancho de árbol acotado que preserve las distancias entre vértices arbitrariamente bien. Debido a esta incrustación, es posible obtener esquemas de aproximación temporal cuasipolinomial (QPTAS) para varios problemas como el viajante de comercio (TSP), el árbol de Steiner , k-mediana y ubicación de instalaciones. ^[5]${\estilo de visualización r}$

Para problemas de agrupamiento como k-Mediana, k-Medias y Ubicación de Instalaciones, se conocen esquemas de aproximación de tiempo polinomial (PTAS) más rápidos para gráficos de dimensión de autopista acotada según la definición 1 anterior. ^[9] Para problemas de diseño de red como TSP y Steiner Tree, no se sabe cómo obtener un PTAS.

Para el problema de k-Center , no se sabe si existe un PTAS para gráficos de dimensión de autopista acotada, sin embargo, es NP-difícil calcular una aproximación ( ) en gráficos de dimensión de autopista , ^[10] lo que implica que cualquier algoritmo de aproximación ( ) necesita al menos el doble del tiempo exponencial en la dimensión de la autopista, a menos que P = NP. ^[10] Por otro lado, se demostró que existe un algoritmo de aproximación parametrizado con un tiempo de ejecución de para k-Center donde es la dimensión de la autopista de acuerdo con cualquiera de las definiciones anteriores. ^[10] Cuando se utiliza la definición 1 anterior, se sabe que existe un esquema de aproximación parametrizado (PAS) cuando se utilizan y como parámetros. ^[11]${\estilo de visualización 2-\varepsilon}$${\displaystyle O(\log ^{2}{n})}$${\estilo de visualización 2-\varepsilon}$${\estilo de visualización 3/2}$${\displaystyle 2^{O(kh\log {h})}n^{O(1)}}$${\estilo de visualización h}$${\estilo de visualización k}$${\estilo de visualización h}$

Para el problema de k-Center capacitado no hay PAS parametrizado por y la dimensión de la autopista , a menos que FPT=W[1] . ^[12] Esto es notable, ya que típicamente (es decir, para todos los problemas mencionados anteriormente), si hay un esquema de aproximación para métricas de baja dimensión de duplicación , entonces también hay uno para gráficos de dimensión de autopista acotada. Pero para k-Center capacitado hay un PAS parametrizado por y la dimensión de duplicación . ^[12]${\estilo de visualización k}$${\estilo de visualización h}$${\estilo de visualización k}$

• Vídeo sobre "Centro k capacitado en baja duplicación y dimensión de autopista" ^[12] presentado por Tung Ahn Vu, 2022.
• Vídeo sobre "Algoritmos para problemas difíciles en gráficos de dimensiones de carreteras bajas" presentado por Andreas Emil Feldmann en ICERM, Universidad de Brown, Providence, EE. UU., mayo de 2019.
• Vídeo sobre "Una incrustación (1 + ε) de gráficos de baja dimensión de autopista en gráficos de ancho de árbol acotado" ^[5] presentado por Andreas Emil Feldmann en el Hausdorff Institut, Bonn, DE, 2015.
• Vídeo sobre “La dimensión de la autopista: de la práctica a la teoría y viceversa” ^[6] a cargo de Andrew Goldberg