メトリックk中心

グラフ理論において、メトリックk中心問題または頂点 k 中心問題は、理論計算機科学で研究されるNP 困難な古典的な組み合わせ最適化問題です。指定された距離を持つn 個の都市が与えられた場合、異なる都市にk 個の倉庫を建設し、都市から倉庫までの最大距離を最小化する必要があります。グラフ理論では、これはk集合内の任意の点から最も近い頂点までの最大距離が最小となるk頂点の集合を見つけることを意味します。頂点はメトリック空間内に存在し、三角不等式を満たす完全なグラフを提供する必要があります。これは、施設の配置とクラスタリングに応用されています。^{[1] [2]}

この問題は1964年にハキミによって初めて提案された。^[3]

を距離空間とし、 を集合、を距離とする。 集合がパラメータ とともに与えられる。目標は、内の点から内の最も近い点までの最大距離が最小となるようなを持つ部分集合を見つけることである。この問題は、次のように正式に定義できる。 距離空間 ( ,d) について、 ${\displaystyle (X,d)}$${\displaystyle X}$${\displaystyle d}$
${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$${\displaystyle k}$${\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }$${\displaystyle |{\mathcal {C}}|=k}$${\displaystyle \mathbf {V} }$${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {X}}}$

• 入力: セット、およびパラメータ。${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$${\displaystyle k}$
• 出力: ポイントのセット。${\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }$${\displaystyle k}$
• 目標: コストd(v, )を最小化する${\displaystyle r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}}$${\displaystyle {\mathcal {C}}}$

つまり、クラスター内の各点はそれぞれの中心から最大で一定の距離だけ離れている。 ^[4]${\displaystyle r^{\mathcal {C}}(V)}$

k-中心クラスタリング問題は、完全無向グラフG  = ( V ,  E ) 上で次のように定義することもできます。三角不等式を満たす距離d ( v _i ,  v _j ) ∈  N
を持つ 完全無向グラフG  = ( V ,  E ) が与えられたとき、 | C | =  kとなるサブセットC  ⊆  Vを見つけ、次の式を最小化します。

${\displaystyle \max _{v\in V}\min _{c\in C}d(v,c)}$

完全無向グラフG  = ( V ,  E ) において、辺を距離の非減少順に並べると、d ( e ₁ ) ≤  d ( e ₂ ) ≤ ... ≤  d ( e _{m ) となり、} G _i  = (V,  E _i )とします。ここで、E _i  = { e ₁ ,  e ₂ , ...,  e _i }です。k中心問題は、 G _{i が}最大でk のサイズの支配集合を持つような最小のインデックスi を見つけることと同等です。 ^[5]

支配集合はNP 完全ですが、k中心問題はNP 困難のままです。これは明らかです。なぜなら、k中心問題に対する与えられた実行可能解の最適性は、まず最適解のサイズ (つまり、G _{i が}最大でサイズkの支配集合を持つような最小のインデックスi ) がわかっている場合にのみ、支配集合削減によって決定できるためです。これはまさにNP 困難問題の難しい核心です。チューリング削減では、 kのすべての値を試すことでこの問題を回避できます。

近似係数 2 を達成する単純な貪欲 近似アルゴリズムは、 k回の反復で最遠点優先のトラバーサルを使用して構築されます。このアルゴリズムは、各反復で現在の中心セットから最も遠い点を新しい中心として選択します。次のように説明できます。 ${\displaystyle {\mathcal {C}}}$

• 任意の点を選択して${\displaystyle {\bar {c}}_{1}}$${\displaystyle C_{1}}$
• 各点について計算する${\displaystyle v\in \mathbf {V} }$${\displaystyle d_{1}[v]}$${\displaystyle {\bar {c}}_{1}}$
• から最も遠い点を選択します。${\displaystyle {\bar {c}}_{2}}$${\displaystyle {\bar {c}}_{1}}$
• これを中心の集合に追加し、この拡張された中心の集合を と表記します。これをk 個の中心が見つかるまで続けます。${\displaystyle C_{2}}$

• i^番目の中心を選択するi^番目の反復には時間がかかります。${\displaystyle {\mathcal {O}}(n)}$
• このような反復はk 回あります。
• したがって、アルゴリズム全体としては時間がかかります。^[6]${\displaystyle {\mathcal {O}}(nk)}$

単純な貪欲アルゴリズムを使用して得られる解は、最適解の 2 近似値です。このセクションでは、この近似係数の証明に焦点を当てます。

距離空間(,d)に属するn個の点 の集合が与えられた場合、貪欲K中心アルゴリズムは、 KがVの最適なk中心クラスタリングの2近似となるようなk中心の集合Kを計算します。 ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$${\displaystyle {\mathcal {X}}}$

すなわち ^[4]${\displaystyle r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} ,{\textit {k}})}$

この定理は次の2つのケースで証明できる。

ケース1: の各クラスターには、ちょうど1つの点が含まれます。${\displaystyle {\mathcal {C}}_{opt}}$${\displaystyle \mathbf {K} }$

• 1つの点を考える${\displaystyle v\in \mathbf {V} }$
• 中心となるのは${\displaystyle {\bar {c}}}$${\displaystyle {\mathcal {C}}_{opt}}$
• の中心は${\displaystyle {\bar {k}}}$${\displaystyle \mathbf {K} }$${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$
• ${\displaystyle d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)}$
• 同様に、${\displaystyle d({\bar {k}},{\bar {c}})=d({\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}}$
• 三角不等式により:${\displaystyle d(v,{\bar {k}})\leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}}$

ケース2: との 2つの中心があり、どちらも にあります。(鳩の巣原理によ​​り、これが唯一の他の可能性です) ${\displaystyle {\bar {k}}}$${\displaystyle {\bar {u}}}$${\displaystyle \mathbf {K} }$${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$${\displaystyle {\bar {c}}\in {\mathcal {C}}_{opt}}$

• 一般性を失うことなく、それが貪欲アルゴリズムによって中心セットに後で追加されたと仮定します。たとえば、i^{番目の反復で追加されます。}${\displaystyle {\bar {u}}}$${\displaystyle \mathbf {K} }$
• しかし、貪欲アルゴリズムは常に現在の中心点から最も遠い点を選択するので、${\displaystyle {\bar {k}}\in {\mathcal {C}}_{i-1}}$

${\displaystyle {\begin{aligned}r^{\mathbf {K} }(\mathbf {V} )\leq r^{{\mathcal {C}}_{i-1}}(\mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}},{\bar {k}})\\&\leq d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}})\\&\leq 2r^{opt}\end{aligned}}}$ ^[4]

同じ近似係数を持つ別のアルゴリズムは、k中心問題が、G _{i が}最大でkのサイズの支配集合を持つような最小のインデックスi を見つけることと同等であるという事実を利用し、 G _iの最大独立集合を計算し、少なくともkのサイズを持つ最大独立集合を持つ最小のインデックスiを探します。 ^[7] P = NPでない限り、任意の ε > 0 に対して近似係数 2 − ε の近似アルゴリズムを見つけることはできません。 ^{[8]さらに、} k中心問題を任意の定数係数内で近似する には、 P = NPでない限り、 G 内のすべての辺の距離が三角不等式を満たしている必要があります。 ^[9]

k をパラメータとすると、任意の ε > 0 に対してk -Center 問題を2 − ε の係数以内で近似するのはW[2] 困難であることが示されます。 ^{[10]これは、} P = NPでない限り、倍増次元（実際にはマンハッタン計量の次元）でパラメータ化した場合にも当てはまります。^[11] kと倍増次元によって与えられた結合パラメータを考慮すると、k -Center は依然として W[1] 困難ですが、パラメータ化された近似スキームを得ることは可能です。^[12]これは、ソリューションの開いた中心にいくつの頂点を割り当てることができるかを制限する頂点容量を持つ変種でも可能です。^[13]

の場合、頂点k中心問題は多項式時間で（最適に）解くことができません。ただし、最適に近い解を得る多項式時間近似アルゴリズムがいくつかあります。具体的には、 2 近似解です。実際、多項式時間アルゴリズムで達成できる最善の解は、2 近似解です。^{[14] [15] [16] [17]頂点}k中心問題などの最小化問題のコンテキストでは、2 近似解は、 となる解です。 ここで、 は 最適解のサイズです。2 近似解を生成することを保証するアルゴリズムは、2 近似アルゴリズムとして知られています。文献で報告されている頂点k中心問題の主な 2 近似アルゴリズムは、Sh アルゴリズム、 ^[18] HS アルゴリズム、^[17]および Gon アルゴリズムです。^{[15] [16]}これらのアルゴリズムは（多項式的に）可能な限り最良のものであるにもかかわらず、ほとんどのベンチマークデータセットでのパフォーマンスは非常に不十分です。このため、多くのヒューリスティックとメタヒューリスティックが開発されてきました。常識に反して、頂点k中心問題に対する最も実用的な（多項式）ヒューリスティックの1つは、3近似アルゴリズムであるCDSアルゴリズムに基づいています^[19]${\displaystyle P\neq NP}$${\displaystyle P\neq NP}$${\displaystyle C'}$${\displaystyle r(C')\leq 2\times r({\text{OPT}})}$${\displaystyle r({\text{OPT}})}$

1995 年にDavid Shmoysによって正式に特徴付けられた^[18] Sh アルゴリズムは、完全な無向グラフ、正の整数、および 最適なソリューションのサイズに関する仮定を入力として受け取ります。 Sh アルゴリズムは次のように動作します。 最初の中心 をランダムに選択します。 これまでのところ、ソリューションは 1 つの頂点 のみで構成されています。 次に、からの距離 が より大きい すべての頂点を含むセットから中心をランダムに選択します。 この時点で、です。 最後に、 が選択したの と同じ方法で残りの中心を選択します 。 Sh アルゴリズムの複雑度は です。ここで、 は頂点の数です。 ${\displaystyle G=(V,E)}$${\displaystyle k}$${\displaystyle r}$${\displaystyle c_{1}}$${\displaystyle C=\{c_{1}\}}$${\displaystyle c_{2}}$${\displaystyle C}$${\displaystyle 2\times r}$${\displaystyle C=\{c_{1},c_{2}\}}$${\displaystyle k-2}$${\displaystyle c_{2}}$${\displaystyle O(kn)}$${\displaystyle n}$

1985 年にDorit HochbaumとDavid Shmoysによって提案されたHS アルゴリズムは、Sh アルゴリズムを基礎としています。^[17]の値は内のいずれかのエッジのコストに等しくなければならないことに注目すると、にはエッジがあるため、HS アルゴリズムは基本的にすべてのエッジ コストで Sh アルゴリズムを繰り返します。HS アルゴリズムの複雑度は です。ただし、順序付けられたエッジ コストのセットに対してバイナリ検索を実行すると、その複雑度は にまで削減されます。 ${\displaystyle r({\text{OPT}})}$${\displaystyle E}$${\displaystyle O(n^{2})}$${\displaystyle E}$${\displaystyle O(n^{4})}$${\displaystyle O(n^{2}\log n)}$

Gonアルゴリズムは、1985年にTeofilo Gonzalez ^[15]とMartin DyerおよびAlan Frieze ^[16]によって独立に提案され、基本的にShアルゴリズムのより強力なバージョンです。 Shアルゴリズムでは の推測が必要ですが、Gonアルゴリズムでは、 よりも距離が大きい頂点の集合が存在する場合、最も遠い頂点はその集合の中になければならないことに着目して、そのような推測を省略します。 したがって、各反復で よりも距離が大きい頂点の集合を計算してからランダムに頂点を選択する代わりに、Gonアルゴリズムでは、すべての部分解 から最も遠い頂点を単純に選択します。 Gonアルゴリズムの複雑度は で、 は頂点の数です。 ${\displaystyle r}$${\displaystyle r({\text{OPT}})}$${\displaystyle 2\times r({\text{OPT}})}$${\displaystyle 2\times r}$${\displaystyle C'}$${\displaystyle O(kn)}$${\displaystyle n}$

2017 年に García Díaz らによって提案された^[19] CDS アルゴリズムは、Gon アルゴリズム (最遠点ヒューリスティック)、HS アルゴリズム (パラメトリック プルーニング)、および頂点k中心問題と支配集合問題の関係からアイデアを取り入れた 3 近似アルゴリズムです。CDS アルゴリズムの複雑度は です。ただし、順序付けられたエッジ コストのセットに対してバイナリ検索を実行することで、CDSh と呼ばれるより効率的なヒューリスティックが提案されています。CDSh アルゴリズムの複雑度は です。CDS アルゴリズムのパフォーマンスは最適ではありませんが、CDSh のヒューリスティックなパフォーマンスは優れていますが、どちらも Sh、HS、および Gon アルゴリズムよりもはるかに優れたパフォーマンスを発揮します。 ${\displaystyle O(n^{4})}$${\displaystyle O(n^{2}\log n)}$

k をパラメータとすると、任意の ε > 0 に対してk -Center 問題を2 − ε の係数以内で近似することはW[2] 困難であることが示されます。 ^{[20]これは、} P = NPでない限り、倍増次元（実際にはマンハッタン計量の次元）でパラメータ化した場合にも当てはまります。^[21] kと倍増次元によって与えられた結合パラメータを考慮すると、k -Center は依然として W[1] 困難ですが、パラメータ化された近似スキームを得ることは可能です。^[22]これは、ソリューションの開いた中心にいくつの頂点を割り当てることができるかを制限する頂点容量を持つ変種でも可能です。^[23]

頂点k中心問題で最も広く使用されているベンチマークデータセットには、OR-Libのpmedインスタンス^{[24]とTSP-Libのインスタンス[25]}があります。表1は、OR-Lib [19]の40のpmedインスタンスに対して各アルゴリズムによって生成されたソリューションの実験的近似係数の平均と標準偏差を示しています^。

貪欲純粋アルゴリズム（またはGr）は、貪欲アルゴリズムの核となる考え方、つまり最適な局所的決定を下すという考えに従います。頂点k中心問題の場合、最適な局所的決定とは、各反復でソリューションのサイズ（カバー半径）が最小になるように各中心を選択することです。言い換えると、最初に選択された中心は、1中心問題を解決する中心です。2番目に選択された中心は、前の中心とともに、最小のカバー半径を持つソリューションを生成する中心です。残りの中心も同様に選択されます。Grアルゴリズムの複雑度はです。^[26] Grアルゴリズムの実験的パフォーマンスは、ほとんどのベンチマークインスタンスで低いです。 ${\displaystyle O(kn^{2})}$

スコアリングアルゴリズム（またはScr）は、2005年にJurij MiheličとBorut Robičによって導入されました。^[27]このアルゴリズムは、頂点k中心問題から最小支配集合問題への縮小を利用しています。この問題は、入力グラフを最適解サイズのすべての可能な値で刈り込み、最小支配集合問題を経験的に解くことで解決されます。この経験的手法は、すべての決定を可能な限り遅くする（貪欲戦略とは対照的）怠惰な原則に従います。Scrアルゴリズムの複雑度はです。Scrアルゴリズムの実験的パフォーマンスは、ほとんどのベンチマークインスタンスで非常に優れています。ただし、入力が大きくなるにつれて、その実行時間は急速に非実用的になります。そのため、小さなインスタンスにのみ適したアルゴリズムであると思われます。 ${\displaystyle O(n^{4})}$

• 巡回セールスマン問題
• 最小kカット
• 支配的なセット
• 独立集合（グラフ理論）
• 施設の立地問題

• Hochbaum, Dorit S. ; Shmoys, David B. (1985)、「k-中心問題に対する最善のヒューリスティック」、オペレーションズ・リサーチの数学、第 10 巻、pp. 180–184、doi :10.1287/moor.10.2.180