高速道路の寸法

ハイウェイ次元の 元の定義^{[ 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)}$。

この定義の変形では半径の球を使用する${\displaystyle cr}$ある定数に対して${\displaystyle c>4}$定数を4より大きい値に選択すると、ハイウェイ次元が制限されたグラフの追加的な構造特性が得られ、それをアルゴリズム的に利用することができる。^{[ 5 ]}

その後の高速道路次元の定義^{[ 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 }$。

この定義は最初の定義よりも弱い。つまり、高速道路次元のすべてのグラフ${\displaystyle h_{1}}$高速道路サイズも備えている${\displaystyle h_{2}}$逆は成り立たない。^{[ 5 ]}

高速道路の寸法の3番目の定義^{[ 7 ]}では、「証拠経路」の概念を導入します。与えられた半径に対して${\displaystyle r}$最短経路${\displaystyle P\in {\mathcal {P}}}$持っている${\displaystyle r}$-目撃者の道${\displaystyle Q\in {\mathcal {P}}}$もし${\displaystyle Q}$長さが${\displaystyle r}$そして${\displaystyle Q}$入手先は${\displaystyle P}$両端に最大 1 つの頂点を追加することで${\displaystyle P}$（つまり、${\displaystyle Q}$頂点数が最大で2つ多い${\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 }$。

この定義は上記の定義よりも強力であり、すなわち高速道路次元のすべてのグラフは${\displaystyle h_{1}}$高速道路サイズも備えている${\displaystyle h_{3}=O(h_{1}^{2})}$、 しかし${\displaystyle h_{1}}$制限することはできない${\displaystyle h_{3}}$[ ^{5 ]​}

より最近の展開^{[ 8 ]}では、近似最短経路を考慮した高速道路次元の緩和された定義が導入されました。この場合、高速道路次元は値ではなく関数であり、任意のに対して次のようになります。${\displaystyle \varepsilon }$ハブ集合の疎性を示します。ここで、${\displaystyle \varepsilon }$実際の最短経路にどれだけ近づけるかを決定します。

重み付きグラフ${\displaystyle G}$高速道路のサイズ${\displaystyle h:\mathbb {R} _{\geq 0}\to \mathbb {N} \cup \{\infty \}}$すべての${\displaystyle \varepsilon \geq 0}$そして${\displaystyle v\in V}$部分集合が存在する${\displaystyle H_{\varepsilon }\subseteq V}$と${\displaystyle |H_{\varepsilon }|\leq h(\varepsilon )}$頂点、ボールの次の特性${\displaystyle B=B_{(4+8\バレプシロン )r}(v)}$成り立つ。すべての頂点のペアについて${\displaystyle u,z\in B}$ 距離が${\displaystyle r}$、${\displaystyle uz}$パス${\displaystyle P}$最大長さ${\displaystyle (1+\varepsilon )}$からの距離${\displaystyle u}$に${\displaystyle z}$、したがって${\displaystyle P}$交差する${\displaystyle H_{\varepsilon }}$。

この緩和は元の定義を一般化し、すべての重複スペースも含む。^{[ 8 ]}

ハイウェイ次元と密接に関連する概念として、最短経路被覆^{[ 1 ]}がある。定義における量化子の順序が逆になっている、つまり、各ボールにハブ集合がある代わりに、ハブ集合が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}$。

境界付き高速道路次元のすべてのグラフ${\displaystyle h}$（上記の定義のいずれに従っても）ローカルにも${\displaystyle h}$-疎${\displaystyle r}$-すべての最短経路カバー${\displaystyle r>0}$逆は成り立たない。^{[ 4 ]}アルゴリズムの目的上、半径ごとに1つのヒットセットを使用する方が便利な場合が多い。${\displaystyle r}$そのため、最短経路カバーは、ハイウェイ次元が制限されたグラフ上のアルゴリズムにとって重要なツールとなります。近似最短経路を使用したハイウェイ次元の緩和された定義でも、疎な最短経路カバーを許容することが示されています。^{[ 8 ]}

最短経路を計算するためのヒューリスティックアルゴリズム（リーチ、コントラクション階層、トランジットノード、ハブラベリングアルゴリズムなど）は、上記の定義3に従って、ハイウェイ次元が制限されたグラフ上で、他の最短経路アルゴリズム（ダイクストラ法など）よりも高速に実行されることが正式に証明できます。 ^{[ 7 ]}

高速道路次元が制限されたグラフに対してアルゴリズム的に利用できる重要な特性は、最短経路カバーのハブから遠い頂点が、いわゆるタウンにクラスター化されることです。^{[ 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}$。

この構造に基づいて、Feldmann ら^{[ 5 ]}は、スプロール現象を指数関数的に増加する値を持つ町に再帰的に分解する町分解を定義した。${\displaystyle r}$定義 1 に従ってハイウェイ次元が制限されたグラフの場合、この分解を使用して、頂点間の距離を任意に良好に保持する、木幅が制限されたグラフへのメトリック埋め込みを見つけることができます。この埋め込みにより、巡回セールスマン(TSP)、シュタイナー木、k-メディアン、施設位置などのさまざまな問題に対して準多項式時間近似スキーム(QPTAS)を取得できます。 ^{[ 5 ]}

k-Median、k-Means、Facility Locationなどのクラスタリング問題では、上記の定義1に従って、高速道路の次元が制限されたグラフに対して、より高速な多項式時間近似スキーム（PTAS）が知られています。 ^{[ 10 ]} TSPやSteiner Treeなどのネットワーク設計問題では、PTASを取得する方法は知られていません。

k-Center問題の場合、高速道路次元が制限されたグラフに対してPTASが存在するかどうかは不明ですが、 (${\displaystyle 2-\varepsilon }$高速道路の寸法のグラフ上の近似${\displaystyle O(\log ^{2}{n})}$[ ^{11 ]これは、}任意の (${\displaystyle 2-\varepsilon }$）近似アルゴリズムは、P=NPでない限り、ハイウェイ次元で少なくとも2倍の指数時間を必要とする。 ^{[ 11 ]}一方、パラメータ化された${\displaystyle 3/2}$-実行時間を持つ近似アルゴリズム${\displaystyle 2^{O(kh\log {h})}n^{O(1)}}$k-Centerが存在し、${\displaystyle h}$上記の定義のいずれかに従って、高速道路の寸法が です。 ^{[ 11 ]}上記の定義 1 を使用する場合、を使用するときにパラメータ化近似スキーム(PAS) が存在することが知られています。${\displaystyle k}$そして${\displaystyle h}$パラメータとして。^{[ 12 ]}

容量付きk-中心問題には、PASは存在しない。${\displaystyle k}$そして高速道路の寸法${\displaystyle h}$FPT=W[1]でない限り。^{[ 13 ]}これは注目に値する。なぜなら、通常（つまり、上述のすべての問題の場合）、低倍化次元のメトリックに対する近似スキームが存在する場合、有界ハイウェイ次元のグラフに対する近似スキームも存在するからである。しかし、容量付きk-センターの場合、PASは次のようにパラメータ化される。${\displaystyle k}$そして倍増次元。^{[ 13 ]}

最近の論文では、近似最短経路を用いて定義した場合、境界付き高速道路次元のグラフにも都市やスプロール現象が見られることが示されました。^{[ 8 ]}この論文では、巡回セールスマン問題（TSP）が高速道路次元でパラメータ化されたPASを許容することも示されています。さらに、パディングされた分解、疎なカバー/パーティション、およびツリーカバーを構築することも可能です。既知の結果に基づいて、多数の応用例が続きます。