数理解析研究所講究録 1297 巻 2002 年 12-23

12
Greedy edge-disjoint paths in complete graphs 1(完全グラフ上の最大辺素パス問題に対する貢欲近似アルゴリズム)
Paz Carmi (Ben-Gurion University of the Negev)
Thomas Erlebach (ETH Zurich)岡本吉央 (Yoshio Okamoto) (ETH Zurich)

概要
最大辺素パス問題 (MEDP) は最も古くから知られる
困難問題の中の一つである. ここでは, 完全グ
ラフ上の MEDP について考察する. Erlebach and Vukadinovic’(2001) は完全グラフ上の MEDP が NP$\mathrm{N}\mathrm{P}$

困難であり, 近似比が定数となる近似アルゴリズムを持つことを示した. 最近の Kolman and Scheideler(2002) の結果は Erlebach and Vukadinovic’ のものよりもよい近似比のアルゴリズムを与えている. 実際,
彼らは (最大辺素パス問題の一般化である) 分割不可能フロー問題に対して 「短縮補題」 を与え, この補題

をうまく用いることでより良い近似比を達成している. 本稿では, 最短路優先責欲アルゴリズムの近似比について議論する. ます, 「短縮補題」 がより良い上界を与えることを観察し, 最短路優先責欲アルゴリズ
ムが 9 近似アルゴリズムであることを示す. 次に, 近似比の下界を与えるインスタンスを構成する.

このインスタンスにより, 最短路優先責欲アルゴリズムの近似比が 3 よりも良くならないことが分かる.

1

イントロダクション

最大辺素バス問題 (maximum edge-disjoint path problem, MEDP) は最も古くから知られる
困難問
題の中の一つである [3]. MEDP はネットワーク上での通信を効率良く行なう問題の幾つかを単純化したモデルであり, 応用上も重要な最適化問題である.
$\mathrm{N}\mathrm{P}$MEDP の定義を述べる. MEDP のインスタンスは無向グラフ $G=(V, E)$ との頂点の非順序対の多重集合 の対 MEDP(G, ) で与えられる.
の各要素はリクエスト (request) と呼ばれる. 考察することは, 共通の辺を持たないパスを用いてより多くのリクエストを結ぶことである. 互いに共通の辺を持た$\mathcal{R}$$\mathcal{R}$$V$$\mathcal{R}$paths) と呼ぶ. MEDP の許容解は の部分多重集合 $A$ と のに属するあるパスで結ばれているよう
辺素パスの集合 の対
で. $A$ に属する各リクエストがにおいてはなものとする. 目的は $A$ のサイズ ( $|A|$ で書き表す) を最大にすることである. 許容解$A$が成り立つことに注意する. リクエストが受理 (accepted) されているとは, それが の要素であることである. 一般性を失わすに,の各リクエストに対してそれを結ぶ のパスが存在すると仮定から取り除いてしまえばよい. )する. (そうでない場合は, そのリクエストを困難であることが知られている [2]. よって, 我々
MEDP は入力のグラフが完全グラフであってもの興味は MEDP に対する近似アルゴリズムに向くことになる. MEDP に対するアルゴリズムが 近似アルゴリズム (
algorithm) であるとは, これが多項式時間アルゴリズムであり, 任意のインを出力することである. ここで, Opt は最適解が受を満たす許容解スタンスに対して Opt
理するリクエストの数である. この のことを近似アルゴリズムの近似比 (approximation ratio) と呼ぶ.
表 1 に完全グラフ上の MEDP に対する近似アルゴリズムをまとめた. 近似比が定数である最初の近似アルゴリズムは Erlebach and Vukadinovic’[2] によって与えられた. このアルゴリズムでは, 最初に頂点集ない複数のパスを辺素バス ($\mathcal{P}$$G$$\mathcal{R}$$\mathrm{e}\mathrm{d}\mathrm{g}\triangleright \mathrm{d}\mathrm{i}\mathrm{s}\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}$$(A, \mathcal{P})$$\mathcal{P}$$(A, \mathcal{P})$$|A|=|\mathcal{P}|$$G$$\mathcal{R}$$\mathcal{R}$$\mathrm{N}\mathrm{P}$$\rho$$\mu \mathrm{a}\mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\leq\rho|A|$$(A, \mathcal{P})$$\rho$

合 $V$ を

$V_{1},$$V_{2},$$V_{3}$という 3 つの概ね等しいサイズの部分に分け,リクエスト$\mathcal{R}$も$\mathcal{R}_{12},\mathcal{R}_{23},\mathcal{R}_{31}$

という 3

に
にもう片方はに属している力 1, あるいは片方は.8 両方ともに対してある手続きを用いて独属しているようなリクエストの多重集合である. そして, それぞれのつの部分に分ける. ここで, 各$\mathcal{R}_{1j}$$V_{j}$$V_{j}$$V_{j}$$\mathcal{R}- j$

lSuPported by the Joint Berlin/Z\"urich Graduate Program “Combinatorics, Geometry, and Computation” (CGC)
financed by ETH Zirich and the German Science Foundation (DFG).

$\not\equiv 1:\dot{\pi}4\Rightarrow F\overline{.7}7\mathrm{A}\sigma)$

立に解を求め,MEDP}}$\mathrm{L}\mathrm{X}\backslash$$\tau$

13.
$\grave{\mathrm{J}}\mathrm{E}\psi\lrcorner^{\backslash }7J\triangleright-\grave{)}|X^{\backslash }\Delta$

3 っの中で一番良いものを出力する. このアルゴリズムを三分割アルゴリズム (tripartition

algorithm) と呼ぶことにするが, ここでは詳細な記述は省略する. 重要なこととして, 彼らはこのア J レゴ
リズムが 27 近似アルゴリズムであることを示している.
MEDP に対する単純なアルゴリズムとして責欲アルゴリズムがある. MEDP に対しては幾つかの変種がある. まず, 我々が見る最初の責欲アルゴリズムは有界長寅欲アルゴリズム (bounded-length greedy

algorith, BGA) である. このア J レゴリズムを図 1 に示しておく. ここで, ステツプ 2-2 こある. の辺の数を表している. BGA を最初に導入したのは Kleinberg[7] である.
はパス : の長さ, つまり,$\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(\pi\dot{*})$$\pi$

BGA はパラメータ$\pi_{1}$$L$を入力で要求していることに注意する.

$. \cdot\frac{\text{ア}/\triangleright \text{ゴ}1/\text{ズム}.\text{有界}\xi*\text{欲ア}J\mathrm{s}\text{ゴ}1J\text{ズム}(\mathrm{B}\mathrm{G}\mathrm{A})}{\lambda\ovalbox{\tt\small REJECT}\cdot ffl\cap \mathrm{p}\text{グ}-\text{フフ}G=(V,E),)\mathrm{t}\text{クエストの多重集^{}\bigwedge_{-}}\mathcal{R}=\{\{s_{1},t_{1}\},\ldots,\{s_{k},t_{k}\}\}}$

パラメータ

出力 :

$A\subseteq \mathcal{R}$$L.\cdot$と G. の辺素パスの集合.

$\mathcal{P}$で$... \frac{A\text{の各^{}1}J\text{クエスト}l^{\mathrm{i}}\mathcal{P}\text{の}’\backslash \text{スで結}\mathfrak{l}\mathrm{f}\text{れて}\mathrm{A}^{\mathrm{a}}\text{る}\mathrm{t}\text{の}-}{\text{ス}\overline{T}^{\backslash }\nearrow\backslash \text{プ}1}$(初期化)$Aarrow\emptyset j\mathcal{P}arrow\emptyset$; $iarrow 1j$

ステップ 2:(主ループ)$\mathrm{w}\mathrm{h}\mathrm{i}\mathrm{I}\mathrm{e}\cdot i\leq k$ステップ 2-1:$s$: と . を結ぶ最短路 : を見つける ;ステップ 2-2:if$\pi$$t_{1}$$1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(\pi_{1}.)\leq L$

then

;
;
;
のすべての辺を取り除く

ステップ 2-2-1:$Aarrow A\cup\{\{s:,t:\}\}$

ステップ 2-2-2:$G$ステップ 2-3:から$\pi_{\dot{*}}$$\mathcal{P}arrow \mathcal{P}\cup\{\pi:\}$$iarrow i+1$ ;end ofステツプ 3:(出力)$\mathrm{w}\mathrm{h}\dot{1}\mathrm{l}\mathrm{e}$;return $A$ およひ$\mathcal{P}.$.

$\cdot$

図 1: MEDP に対する有界長責欲アルゴリズム.
Д薀瓠
Kolman and Scheideler [8] はフロー数 (flow number) と呼ばれるネットワーク \iota こ対する新しを導入し, パラメータ $L=4F$ の BGA が分割不可能フロー問題 (unsplittable flow problem, MEDP
タの一般化) に対する $(16F+1)$ 近似アルゴリズムであることを示した. 実際, 彼らは 「短縮補題 (shortening
lemma)\rfloor を示し, この補題をうまく用いることでより良い近似比を達成して る. 後程, 完全グラフのフロー数力火であることを示す. すなわち, 彼らの結果から完全グラフ上の MEDP }r こ対する 17 近似ア J レゴ$\mathrm{A}\mathrm{a}_{J}$$F$$\mathrm{A}\mathrm{a}$

リズムが出来る.

他の種類の責欲アルゴリズムとして. 最短路優先貢欲アノレゴ 1 ノズム (shotest-path-first greedy algorithm,
で選ぶ候SGA) がある. 図 2 にアルゴリズムの詳細を示しておく. このアルゴリズムでは, ステツプ 2-1

14
補が複数あるとき, その中のどれか一つを任意に選ぶものとする. ステップ 2-4 も同様に実行するとする.

このアルゴリズムを最初に導入したのは Kolliopoulos and Stein[6] である.
アルゴリズ A :最短路優先アルゴリズム (SGA)

入力

無向グラフ $G=(V, E)$ とリクエストの多重集合

出力 :

と

$A\subseteq \mathcal{R}$

$A$

$G$

の辺素パスの集合の各リクエストが$\mathcal{P}$.;$\mathcal{R}$で$\mathcal{P}$のあるパスで結ばれているもの :ステップ 1:(初期化); $iarrow 0j$$Aarrow\emptyset$

ステップ 2:(主ループ)$\mathrm{w}\mathrm{h}\dot{1}\mathrm{l}\mathrm{e}\mathcal{R}$ステップ 2-1:のリクエストの中に $G$ のパスで結ばれているものがある$\{s:,t:\}arrow \mathcal{R}$のリクエストでステップ 2-2 :$Aarrow A\cup\{\{s:,t:\}\}j$ステップ 2-3 :$\mathcal{R}arrow \mathcal{R}\backslash \{\{s_{i},t|.\}\},\cdot$

ステップ 2-4:$\pi_{i}arrow s_{i}$ステップ 2-5:
ステップ 2-6 :$\pi_{i}$

$s$

: と

$t_{:}$

を結ぶ最短路の長さがの他のリクエストを結ぶ最短路の長さを越えないもの ;$\mathcal{R}$と$t_{i}$

を結ぶ $G$ 上の最短路の全ての辺を$G$$j$から取り除く ;$iarrow i+1,\cdot$;
end ofステップ 3:(出力)return $A$ およひ$\mathrm{w}\mathrm{h}\dot{1}\mathrm{l}\mathrm{e}$$\mathcal{P}arrow\{\pi_{\dot{\mathrm{r}}} :\{sj, t:\}\in A\}$.

図 2: MEDP に対する最短路優先責欲アルゴリズム.

SGA が 9 近似アルゴリズムであることを示す. 特筆しておきたい

本稿では, 短縮補題を用いることで,こととして, Erlebach and Vukadinovic’[2] は SGA が 54 近似アルゴリズムであることを示している.
も SGA の近似で表記する) を考え,
更に. 別の上界を得るためにリクエストの最大多重度 ($\mu_{\max}$$\mu_{\mathrm{m}\mathrm{a}\mathrm{J}\epsilon}$比の上界であることを示す. よって, 次の定理を得ることになる.
定理 Ll (主結果). 最短路優先責欲アルゴリズムは完全グラフ上の最大辺素近似アルゴリズムである.

$!^{\backslash }0$ス問題に対する $\min\{9,\mu_{\max}\}$

次のステップとして, 近似比の下界を考察する. 本稿では, 完全グラフ上の MEDP のインスタンスで

SGA の近似比が 3 より良くならないものを構成する.
本稿の構成は以下の通りである. より良い上界 (定理 1.1) の証明は次の節で行なう. 第 3 節で T 界を与えるインスタンスを構成する. 最後の節で補足を幾つか加える.

記法

有限 (多重) 集合 $S$ のサイズ, すなわち $S$ の要素数を $|S|$ で表す. 実数全体の集合を

負実数全体の集合を町で表す. パス$P$をそのパスに沿って順に辿っていった頂点$(v_{1}-v_{2}-\cdots-v_{l})$ のように書き表すことがある.

で表す. 二つのパスというのは,

で表す.

$p$

と

$q$

$p$

と

$q$

に対して,

$p\cap q$

で $p$ とが辺素であることを意味する.

$q$

パス $p$ の長さ,すなわち,

$v_{1},$ $v_{2},$$p$$\mathrm{R}$$\ldots,$

で表し, 非$v\iota$を使って,の辺の数を length(p)が共通 [こ持つ辺の集合をあらわす. よって, $p\cap q=\emptyset$

パス $p$ と辺$e$}こ対して,

最後に, 「 $A:=B\mathrm{J}$ で「 $A$ を $B$ で定義する」 ことを表す.

$e$が $p$ の辺であることを $e\in p$

152$[perp] \mathrm{f}\mathrm{f}$

本節では, 完全グラフ上の MEDP の近似比の上界を改良する. 最初の小節では, Kolman and Scheideler[8] の枠組の中から特にフロー数ど短縮補題を説明し, 彼らの結果から直ちに近似比が改良できることを見る. すなわち, パラメータ $L=4$ の BGA が完全グラフ上の MEDP に対する 17 近似アルゴリズムであるが9ことを示す. 二つ目の小節では, 更に改良することを目指し, 完全グラフ上の MEDP に対して近似アルゴリズムであることを示し, 主定理 (定理垣) を証明する.
$\mathrm{S}\mathrm{G}\mathrm{A}$2.1

完全グラフのフロー数

Kolman and Scheideler [8] の最近の研究では, ネットワークのフロー数 (flow number) と短縮補題(shortening lemma) を用いて, 分割不可能フロー問題 (unsplittable flow problem, UFP) に対する近似アルゴリズムの近似比を改良している. ここでは, 彼らの結果の紹介から始める.
UFP は MEDP の一般化である. ます, 与えられているのは無向グラフ $G=(V, E)$ と関数 $u:Earrow 1\mathrm{R}+$である. 辺 $e\in E$ に対して, $u(e)$ は の容量 (capacity) と呼ばれる. また, MEDP と同様にリクエスト
$e$

の多重集合

$\mathcal{R}$も与えられる. 更に,$d$:R\rightarrow 町と$r$:R\rightarrow 町という二つの関数も与えられる.

リクエの需要 (demand) と利益 (profit, reward) と呼ばれる. まit リクエス$u,$ $d,$) で与えられ, $G$ は無向グラフ,
とめると, UFP のインスタンスは 5 つ組 UFP(G,の部分多重集合 $A$ と $G$ の (必は需要, H ま利益である. UFP の許容解はは容量,トの多重集合,のあるパスで結ばれて ゝ
で, $A$ の各リクエストがすしも辺素とは限らない) パスの集合 の対
スト$i\in \mathcal{R}$に対して,$d(i)$と $r(i)$ はそれぞれ$i$$\mathcal{R}$$r$$\mathcal{R},$$\mathcal{R}$

$d$

$u$

$\mathrm{A}$て, かつ, それぞれの辺 $e\in E$ に対して,$\mathcal{P}$$(A,\mathcal{P})$$\mathcal{P}$$e$を通るパスで結ばれたリクエストの需要の和が の容量 $u(e)$$e$以下であるようなものとする. リクエストが受理 (accepted) されているとは, それが $A$ に属して$\mathrm{A}\mathrm{a}$るこ

目的は, 受理されたリクエストの利益の総和を最大化することである. MEDP が UFP の特殊に対して $d(i)=r(i)=1$ とす
ケースであることは, すべての $e\in E$ に対して $u(e)=1$ , すべてのとである.

$i\in \mathcal{R}$ることで分かる.
困難問題であることは, UFP が MEDP を特殊ケースとして含むことから分かる. ここでUFP がは, UFP に対する近似アルゴリズムを定義する. (先程の節では, MEDP に対する近似アルゴリズムし力 ‘algorithm)
定義していなかった. )UFP に対するアルゴリズムが 近似アルゴリズム (を満であるとは, これが多項式時間アルゴリズムであり, 任意のインスタンス こ対して Opt$\mathrm{N}\mathrm{P}$$\mu \mathrm{a}\mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\rho$$\leq\rho.\sum_{1\epsilon A}r(i)$を出力することである. ここで, Opt は最適解力 I 受理するリクエストの II 益のたすような許容解総和である. MEDP のときと同様に をこのアルゴリズムの近似比 (approximation ratio) と う.
多くの組合せ最適化問題と同様に, UFP は {0, 1} 整数計画問題として記述できる. この記述のため [こ,二種類の変数を用意する. 一つ目は $x\in\{0,1\}^{R}$ で, リクエス加が受理されるとき $x:=1$ で. そうでな$(A, \mathcal{P})$$\mathrm{A}\mathrm{a}$$\rho$

いとき $x:=0$ となるものとする. 二つ目の変数は$y^{(:)}\in\{0,1\}^{\mathcal{P}:}$で, ここで,ス加を結ぶ $G$ 上のパス全体の集合である. 変数

の意味は,

リクエスト

理されるとき$y_{\pi}^{(-)}=1$

で. そうでないとき$y^{(:)}$$y_{\pi}^{(\dot{\iota})}=0$となることである.

$i\in \mathcal{R}$$i$力$\mathrm{i}/$であり,$\text{ス}$$\pi\in \mathcal{P}_{i}$:}まリクエ$\mathcal{P}$

を使って受

UFP

$\mathrm{k}\mathrm{g}\mathrm{a}\mathrm{e}_{\beta}\neq\Phi \mathbb{H}\mathrm{E}k\mathrm{b}T\not\in \mathrm{R}l\mathrm{b}\mathrm{b}t_{-}^{\vee}\sigma$

IP-UFP(G,$\mathcal{R},u,$$d,$ $r$)$l^{\mathrm{i}}\mathfrak{R}^{-}\mathrm{C}\hslash$):maximize$\sum_{j\in R}r(i)x$

16

.

:

subject tofor all $e\in E$ ,(1)

$j \epsilon \mathcal{R}\pi\in \mathcal{P}:\epsilon.\mathrm{t}.\mathrm{e}\epsilon\pi\sum_{1}d(i)y_{\pi}^{(j)}\leq u(e)$$\sum y_{\pi}^{(i)}=x$$\pi\in \mathcal{P}$:for all$i\in \mathcal{R}$,(2)

for all$i\in \mathcal{R}$,(3)

for all$i\in \mathcal{R}$:. $\in\{0,1\}$$x_{1}$$y_{\pi}^{(1)}.\in\{0,1\}$

and$\pi\in \mathcal{P}_{i}$.

(4)$u,$ $d,$
この定式化 IP-UFP(G,) は理解しやすいが, 変数の数が指数関数的になっている. しかし, ネッ
トワークフロー問題のときと同様に, 多項式サイズの定式化も得ることが出来る. 例えば, [5] を参照.
では. {0, 1} 制約式 ((3) と (4)) を緩和. すなわち, これらの制約式を $x;\in[0,1]$ と $y_{\pi}^{(-)}\in[0,1]$ に置き$r$$\mathcal{R},$

換えてみる. このようにして, 多品種フロー問題 (multicommodity flow problem) と呼ばれる線形計画問$u,$ $d,$) で表す.
題が得られる. この問題を LP-UFP(G,$r$$\mathcal{R},$

多品種フロー問題の変種として, 並行多品種フロー問題がある. 並行多品種フロー問題 (concurrent

multicommodity flow problem) とは次のように定義される問題である.

Con MFP(G,maximize$\mathcal{R},$$u,$ $d,$ $r$):$x_{1}$

for all $e\in E$ ,subject to$: \epsilon..\mathcal{R},\pi\epsilon \mathcal{P}:\sum_{\mathrm{t}.\mathrm{e}\epsilon\pi}d(i)y_{\pi}^{(i)}\leq u(e)$,for all$i\in \mathcal{R}$$X:=X_{j}$for all$i,j\in \mathcal{R}$$0\leq x:\leq 1$

for all$i\in \mathcal{R}$$0\leq y_{\pi}^{()}\leq 1$

for all$i\in \mathcal{R}$$\sum y_{\pi}^{()}=x$:$\sim\epsilon\nu.\cdot$

(5)

,

,
and

$\pi\in \mathcal{P}_{1}.$.

の値が制約 (5) によって同じ$u,$) の許容解では, すべての並行多品種フロー問題 ConMFP(G,になっている. つまり, この問題は, すべてのリクエストが同じ割合だけ受理されることを強制されている場合にその割合をどれだけ大きくすることができるかを考える問題である. 並行多品種フロー問題) の許容解にもなってい
$u,$
$u,$
) の許容解は対応する多品種フロー問題 LP-UFP(G,ConMFP(G,$\mathcal{R},$$d,$ $r$$d,$ $r$$\mathcal{R},$$x_{i}$$\mathcal{R},$$d,$ $r$

ることに注意する. 但し, 逆は成り立つとは限らない.
では, ネットワークのフロー数を定義しよう. (ここで, ネットワーク (network) とは無向グラフ $G=(V, E)$と容量関数 : $Earrow \mathbb{R}$ の組 $(G, u)$ のことである. ) 無向グラフ $G=(V, E)$ と容量関数 : E\rightarrow 町が与えられている. ここで, 並行多品種フロー問題のインスタンス ConMFP(G, ) を構成する. リクエ
ストの集合 は頂点の全ての非順序対で成り立つ, つまり, $\mathcal{R}=\{\{s, t\} : s, t\in V, s\neq t\}$ とする. 需要
$u$

$u$

$u$

$\mathcal{R}$$d:\mathcal{R}arrow \mathrm{R}_{+}$は$‘ \sum_{\{,v\}\in B}u(\{s, v\})\sum_{\{tv\}1\in B}u(\{t, v\})$$d(\{s,t\}):=$

で定義し, 利益$r$2$\sum_{e\epsilon B}u(e)$:R\rightarrow 町は$d$と同じである, つまり, すべての$i\in \mathcal{R}$に対して $d(i)=r(i)$ であると

17
する. このよう [こして, 並行多品種フロー問題のインスタンス ConMFP(G, )$u$$=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{M}\mathrm{F}\mathrm{P}(G, \mathcal{R}, u, d, r)$を得る.
に対して, 緩慢度と過密度という二つのパラメー
並行多品種フロー問題の許容解 $\xi=$$D(\xi)$の中のパスの最大長である, すなわち,とはタを導入する. 許容解 の緩慢度 (dilation)$(x, (y^{(j)} :i\in \mathcal{R}))$

$\xi$

$\xi$

$D( \xi):=\max\{\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(\pi)$

許容解

$\xi$

:

.

$y_{\pi}^{(\dot{*})}>0\}$の過密度 (congestion) $C(\xi)$ とは$C( \xi):=\frac{1}{x_{1}}$の目的関数値の逆数である, すなわち,

$\xi$

.

ネットワーク $(G, u)$ のフロー数 (flow number) とは次で定義される量 $F(G, u)$ のことである.

{$F(G, u):= \min$ $\max\{D(\xi),$ $C(\xi)\}$ :は ConM$\xi$$\mathrm{F}\mathrm{P}(G,$の許容解 }.

$u)$

ネットワークのフロー数は容量のスケーリングに対して不変であることに注意する.
ここで, 単位容量の完全グラフに対して, そのフロー数を定める.

補題 21(完全グラフのフロー数). $G=(V, E)$ を完全グラス$u(e)=1$ であるとする. このとき, $F(G, u)=1$ が成り立つ.

$u$: E\rightarrow 町をすべての $e\in E$ に対して

証明. まず. ConMFP(G, ) が何になるかを調べる. リクエストの集合$u$$\mathcal{R}$は $E$ であり, 需要は各$\{s,t\}\in \mathcal{R}$に対して, $d(\{s,t\})=(n-1)/n$ で定められる.

MFP(G, ) の許容解とする. このとき,$\max\{D(\xi), C(\xi)\}\geq C(\xi)=1/x_{1}\geq 1$ となる. すなわち, 次が成立する.
ここで,$\xi=(x, (y^{(:)}i\in \mathcal{R}))$

{
{ :

を

$u$

$\mathrm{C}\mathrm{o}\mathfrak{n}$$F(G, u)= \min$ $\max\{D(\xi),$ $C(\xi)\}$ :$\geq\min$

$1$

$\xi$

は Con

$\xi$

は Con MFP(G,$u$$\mathrm{M}\mathrm{F}\mathrm{P}(G,$$u)$$0\leq x_{1}\leq 1$であるから,の許容解}) の許容解} $=1$ .

MFP(G, ) の許容解で, 任意のリクエス加 $=\{s, t\}$ と任意の力|
パス $\pi=(s-t)\in$ 乃に対してで他の全ての変数は 0 としたものとする. (実際,ConMFP(G, ) の許容解であることは簡単に確認できる. ) このとき, $D(\xi’)=C(\xi’)=1$ が成立するので,
次に, 逆向きの不等式を示す.

$\xi’$を$u$$\mathrm{C}\mathrm{o}\mathrm{n}$$\xi’$$y_{\pi}^{(\cdot)}.=x_{\dot{*}}=1$$u$$F(G, u)= \min$ { $\max\{D(\xi),$ $C(\xi)\}$ :

$\xi$

は Con

$\mathrm{M}\mathrm{F}\mathrm{P}(G,$

$u)$

の許容解}

$\leq\max\{D(\xi’), C(\xi’)\}=1$

口となる. これで証明が完結した.
フロー数を用いることで,Kolman and Scheideler [8] は興味深い定理を示している. 一つは, y‘わゆる「短縮補題」 である.
補題 22(短縮補題 [8]). 並行多品種フロー問題のインスタンスで, 需要と利益力|一致し, 力 ‘つ, フローの数が $F$ であるようなものを とする. このとき. 目的関数値が $f$ となる の任意の許容解に対して,
許容解 で, 目的関数値が $f/(1+\epsilon)$ で緩慢度が $D(\xi)\leq 2(1+1/\epsilon)F$ であるものが存在する.
$I$

$I$

$I$

$\xi$

とする. UFP の許容解が与えられているときに, その許容解を, 対応する多品種フロー問題の許容の長さが $4F$ 以下であるもの}こ変換できること力|短縮
解で, 目的関数値は元の解の半分だけども, 使う$\epsilon=1$$J\backslash \cdot \text{ス}$

補題を用いると分かる. どうしてそうなるかを説明する. UFP のインスタンスとが与えられていて, $(x, (y^{(:)} : i\in \mathcal{R}))$ を に対する許容解とする. このときに,) を考える. ここで, すゝての$u,$ $d,$
MFP(G,
め, 並行多品種フローのインスタンスとして$I=\mathrm{I}\mathrm{P}- \mathrm{U}\mathrm{F}\mathrm{P}(G,\mathcal{R}, u, d, d)$$\overline{\mathcal{R}}:=\{i\in \mathcal{R} :$I$$\overline{I}=\mathrm{C}\mathrm{o}\mathrm{n}$に対して$\overline{x}:=x:$, すべての $i\in$ 児と: に対して$\pi\in \mathcal{P}$$\overline{y}_{\pi}^{(-)}=y_{\pi}^{(\dot{\iota})}$$i\in\overline{\mathcal{R}}$$d$$\overline{\mathcal{R}},$と$\mathrm{A}\mathrm{a}$うものを考えると?

$\text{定}$x:=1\}$$(\overline{x}, (\overline{y}^{(1)}.

:i\in\overline{\mathcal{R}}))$

18
は$\overline{I}$の許容解で, 目的関数値は 1 になる. 今, 短縮補題をこの解に適用する. そうすると,$\overline{I}$の許容解で,

目的関数値が 1/2, 緩慢度が $4F$ 以下のものが存在することが分かる. この解は元の UFP のインスタンス$u,$) でもあり, 目的関数値は元の解の値の半分に対応する多品種フロー問題の許容解 LP-UFP(G,$I$$\mathcal{R},$$d,$ $d$

で, 緩慢度は $4F$ 以下になっていることになる.

この補題を用いて, Kolman and Scheideler [8] は別の面白い定理を示した. これはフロー数を使って近似比の上界を与えている.
補題 23(フロー数を用いた UFP に対する上界 [8]). 分離不可能フロー問題のインスタンスで, 次の三条件を満たすものを考える. (1) 任意のリクエストに対して要求と利益が等しい. (2) 要求の最大値が容量の最小値以下である. (3) フロー数が $F$ である. このとき, 適当に番号づけを変更すると, パラメータを$4F$ とする有界長責欲アルゴリズムは上の条件を満たす分離不可能フロー問題に対する $(16F+1)$ 近似ア
ルゴリズムになる.

この補題において, 「適当に番号づけを変更する」 ということはリクエストの番号を次のように変えることである : 任意の二つのリクエス加と に対して, \prec i)>r(力ならば は の前に来る. この補題は
$i$

$j$

$j$

SGA に対しても戒立することに注意する.
単位容量の完全グラフのフロー数は 1(補題 2 力であり, MEDP は補題 23 にある三条件を満足するので, 次の結果が直ちに得られる.

定理 24(完全グラフ上の MEDP に対する BGA の近似比). パラメータを $L=4$ とする有界長責欲ア

ルゴリズムは完全グラフ上の最大辺素パス問題に対する 17 近似アルゴリズムである.
この結果も SGA に対して成立する. 次の小節で, この上界を改善する.

9 近似アルゴリズム

2.2

ここで, 完全グラフ上の MEDP に対して SGA が 9 近似アルゴリズムであることを示す. もう一度,

MEDP は UFP の特殊ケースであることに注意しておく.
補題 25(MEDP に対する上界の改善). 最短路優先責欲アルゴリズムはフロー数 $F$ の無向グラフ上の最大辺素パス問題に対する $(8F+1)$ 近似アルゴリズムである.
証明. $(A,\mathcal{P}(A))$ を SGA によって得られた許容解とする. つまり. $A$ は SGA が受理したリクエストの多はそれらを結ぶ辺素パスの集合である. また, $O$ で最適解が受理する ) クエストの多重
重集合で,
$1$

$\mathcal{P}(A)$集合を表す. 短縮補題 (補題 22) によって, 対応する多品種フロー問題の許容解 $\xi=(x, (y^{(:)} : i\in \mathcal{R}))$ で,
目的関数値が $|O|/2$ で, なおかつ, $D(\xi)\leq 4F$ となるものが存在することが分かる.
でを満たすパス全体の集合を表すことにする. また, $\mathcal{P}\leq 4F(A):=\{p\in \mathcal{P}(A)$ : length(p)\leq$\mathcal{P}(\xi)$$4F\}$$y_{\pi}^{(-)}>0$と定義し, 任意にパス$p\in \mathcal{P}\leq 4F(A)$を取って来る. このとき, 式 (1) を使うと,(6)$\mathrm{s}.\mathrm{t}.\pi\cap p\neq\emptyset\sum_{\pi\in \mathcal{P}(\xi)}y^{(}i^{)}\leq\sum_{8}.\sum_{\in e\in p\pi \mathcal{P}(\xi)}y_{l}^{(i)}=\sum_{8}.\sum_{\mathcal{R},e\in pi\epsilon\pi\epsilon \mathcal{P}}y_{\pi}^{(j)}\leq\sum_{\mathrm{e}\in p}1\leq \mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(p)$が成立することが分かる.
今,を次のように二つの部分$\mathcal{P}(\xi)$$\mathcal{P}_{1}(\xi)=${$\pi\in \mathcal{P}(\xi)$:$\mathcal{P}_{2}(\xi)=\mathcal{P}(\xi)\backslash \mathcal{P}_{1}(\xi)$$\pi$$\mathcal{P}_{1}(\xi)$と$\mathcal{P}_{2}(\xi)$に分割する.

が結ぶリクエストが $A$ の要素ではない },.

このとき, 次の要請が成り立つことを確認する.

19
要請 25.1. それぞれのパス
ち,

$\pi$

$\pi\in \mathcal{P}_{1}(\xi)$と $p$ が共通の辺を持つ. 更に,$p$

に対してあるパス$p\in \mathcal{P}(A)$が存在して$\pi\cap p\neq\emptyset$となる, すなわの長さは $4F$ 以下である.

要請の証明. 最初の部分については, そうでないと仮定して考える. すると,ない辺だけから成り立つパスがあるリクエスト$r\in \mathcal{R}\backslash A$$\mathcal{P}(A)$のどの J$\backslash ^{o}\text{ス}$も使っていを結んでしまうことになる. そうなると, SGA

はこのリクエストを受理しないといけなかったことになり, 矛盾.
二つ目の部分については, もしそのようなすべてのパスの長さが $4F$ より長ぶリクエストを受理する代わりに

$\pi$

とすると,

$\mathrm{A}\mathrm{a}$$\mathrm{S}\mathrm{G}\mathrm{A}|\mathrm{h}p$が結ぶリクエストを受理しないといけなかったことになり,

力 |結

また矛盾

となる.

$\square$では, 近似比を解析しよう. ます, 要請 2.5.1 と式 (6) を用いて,length(.p)\leq 4F$|\mathcal{P}\leq 4F(A)|\leq 4F|\mathcal{P}(A)|=4F|A|$$\sum_{\pi\epsilon \mathcal{P}_{1}(\xi)}y_{\pi}^{(1)}.\leq\sum_{4p\epsilon F(A)}\sum_{\pi p_{\leq}\in \mathcal{P}(\zeta)}y_{\pi}^{(\dot{l})}\mathrm{s}.\mathrm{t}.\pi\cap p\neq\emptyset\leq\sum_{p\in p_{\leq}4F(A)}$を得る. 次に,$y_{\pi}^{(j)}\leq|A|/2$$\sum$$\pi\in \mathcal{P}_{2}(\xi)$が成立することが分かる. ゆえに,

Opt $=|O|=2\mathrm{x}$ (the objective value for )$\xi$$=2 \sum_{\epsilon \mathcal{R}}\sum_{\pi\in \mathcal{P}}.\cdot y_{\pi}^{(\dot{l})}=2\sum_{\pi\epsilon \mathcal{P}(\xi)}y_{\pi}^{()}$$=2( \sum_{\pi\in \mathcal{P}_{1}(\xi)}y_{\pi}^{(\dot{\iota})}+\sum_{\pi\in \mathcal{P}_{2}(\xi)}y_{\pi}^{())}\leq 2(|A|/2+4F|A|)=(8F+1)|A|$口となり, 近似比が $8F+1$ になることが示された.

この解析はパラメータを $L=4F$ とする BGA にも適用できることを補足しておく.
補題 21 と 25 から直ちに次の系を得る.
系 26(完全グラフ上の MEDP に対する上界の改善). 最短路優先責欲アルゴリズムは完全グラフ上の最大辺素パス問題に対する 9 近似アルゴリズムである.

リクエストの多重集合 を考える. リクエス
[こお る $\{s,t\}$ の多重度 (multiplicity) E ま
個持っているとき,別の上界を得るために, リクエストの多重度を定義する.
ト$\mu$$\{s,t\}\in \mathcal{R}$に対して,$\mathcal{R}$が $\{s,t\}$ をである, と言うことにする. 例えば,$\mathcal{R}$$\mathcal{R}$$\mu$$\mathrm{I}\mathrm{e}$$\mathcal{R}=\{\{1,2\}, \{1,2\}, \{2^{\cdot}, 4\}, \{3,4\}, \{3,4\}, \{3,4\}\}$の多重度は 2, {2, 4} の多重度は 1, {3, 4} の多重度は 3 となること力|分力 1 る.
クエストの多重度の最大値を表すことにする. 混乱の危険がない場合には, 単にでは, $\mu_{\max}=3$ になる.

$\mu_{\max}(\mathcal{R})$ーこで,$\mu_{\max}$が小さいときには近似比が少し良くなることを見る.

であるとする. 先程の例では,$\mathcal{R}_{1}=\{\{1,2\}, \{2,4\}, \{3,4\}\}$

補題 27(SGA の出力の性質). 完全グラフ上の最大辺素’ くであるとき,$(^{*})$

更に, 条件$\mathcal{R}_{1}$を$(^{*})$

で$\mathcal{R}${1, 2}

t こお|するリと書く. 先程の例の多重度を無視した集合$\mathcal{R}$となる.
$\text{ス}$問題}こ対して,最短路優先責欲アルゴリズムが受理するリクエストの多重集合$\mathcal{R}_{1}$$\mu_{\max}$とすると,力 ) クエストの多重集合$\mathrm{i}$$\mathcal{R}$$A$$\mathrm{t}$t2 次の条件を満たす.

の各リクエストは長さ 1 のパス (つまり, ただの 1 辺) で結ばれて受理される.

を満たす最適解が存在する.

証明. 容易なので省略する.

口

20
つまり,

$|\mathcal{R},|\ovalbox{\tt\small REJECT}|A|$が成立する. 更に,$7^{\ovalbox{\tt\small REJECT} \mathrm{j}} \max|\mathcal{R},|$は$|\mathcal{R}|$の上界であり,$|\mathcal{R}|$は Opt の上界である.

よって, 近似比が次のように解析できる.

Opt$\leq|\mathcal{R}|\leq\mu_{\max}|\mathcal{R}_{1}|\leq\mu_{\max}|A|$.

この解析と系 26 を合わせることで, 定理 1J が得られる.

3

下界
前節では,

SGA が

$\mathrm{m}\mathrm{i}\mathrm{n}${ , pmゎ} 近似アルゴリズムになることを示した. では, この近似比はどこまで$9$

良くすることが出来るのだろうか. つまり, 本当の近似比は何なのだろうか. この値以下に近似が下げられないことを示すインスタンスはまだ見つかつていない. ただ, 近似比が 9 より小さくならないインスタ

ンスではリクエストの最大多重度が 9 以上でないといけないことに注意しておく.
この節では, 完全グラフ上の MEDP のインスタンスを二つ構成する. 最初のものは, $\mu\max=2$ で近似という近似比になる.
に対して比が 4/3 になる. 次のものは, hゎは任意に大きく, 小さい$\epsilon>0$31のインスタンス$\mu_{\max}=2$

この小節では, 完全グラフ上の MEDP のインスタンスで,$h\text{ゎ}=2$$3-\epsilon$$\mu_{\mathrm{m}\mathrm{a})(}=2$になっているものを構成して,のときに SGA の近似比が 4/3 より良くならないことを示す ここで構成するインスタンスは頂リクエストの数は 16 である. 最適解ではすべてのリクエストを受理するが, SGA は 12個しか受理しない可能性がある. よって, その比が 4/3 になる.
点数 8 のもので,頂点集合を $V=\{1,2,3,4,5,6,7,8\}$ とする. 16 個のリクエストは次のように与えられる.
$r_{1}:=\{1,3\}$,$r_{2}:=\{1,3\}$,$r_{3}:=\{5,3\}$,$r_{4}:=\{5,3\}$,$r_{5}:=\{1,7\}$,$r_{6}:=\{1,7\}$,$r_{7}:=\{5,7\}$,$r_{8}:=\{5,7\}$,$r_{9}:=\{2,4\}$,$r_{10}:=\{2,4\}$,$r_{11}:=\{8,6\}$,$r_{12}:=\{8,6\}$,$r_{1\theta}:=\{3,8\}$,$r_{14}:=\{3,6\}$,$r_{15}:=\{7,2\}$,$r_{16}:=\{7,4\}$.

多重集合 はこの 16 個のリクエストから成り立っていて, $h\text{。}=2$ であることが分かると思う. 図 3に, 16 個のリクエストが頂点数 8 の完全グラフ上にどのように分布しているか描いてある. ここで, それは $\{s:,ti\}$ として記述されていて, 頂点は一番上が 1 で反時計回り順に番号を付けてぞれのリクエスト$\mathcal{R}$

$rj$

ある.

補題 27 より, SGA の出力と最適解では,タンスにおいては,ストを$\mathcal{R}$$\mathcal{R}_{1}$の各リクエストを対応する 1 辺で受理する. このインスである. よって, ます, これらのリクエ$\mathcal{R}_{1}=\{r_{1}, r_{3}, r_{5}, r\tau, r_{9}, r_{11}, r_{13}, r_{14}, r_{15}, r_{16}\}$から取り除いて, 使用した辺もグラフから取り除くことにする.

最適解が残りのリクエストをすべて受理することを見よう. そのためには, 最適解は次のようなパスを使えばよい.
では,

リクエスト
リクエスト
リクエスト

$r_{2}$$r_{4}$$r\epsilon$

をパス (1–2–3) で結ぶ.

をパス (5–4–3) で結ぶ.
をパス (7–8–1) で結ぶ.
をパス (5–6–7) で結ぶ.

リクエスト

$r_{8}$

リクエスト$r_{10}$

リクエスト$r_{12}$をパス (2–8–4) で結ぶ.
をパス (6–1–5–8) で結ぶ.

21,
$s_{7}^{3},s_{8}^{4}s,s$

図 3: 頂点数 8 で $\mu_{\max}=2$ のインスタンス.

SGA が受理するリクエストを考える. これを考えるために, ます, まだ受理されていないリクエ

次に,ストを結ぶ最短路の長さを計算する.
$r_{2}$$r_{4}$$r_{6}$$r_{8}$

に対して, (1–2–3) が最短路で長さは 2.
に対して, (5–4–3) が最短路で長さは 2.

に対して, (1–8–7) が最短路で長さは 2.

に対して, (5–6–7) が最短路で長さは 2.

$r_{10}$$r_{12}$に対して, (2–3–4) が最短路で長さは 2.
に対して, (8–7–6) が最短路で長さは 2.

これらのどのリクエストも SGA が次に受理する候補なので, ここでは
リクエスト
$r_{2}$$r_{4}$$r_{10}${3, 4} を取り除く. すると,と 2 辺 {2, 3},$r_{2}$と$r_{4}$$r_{10}$を選ぶことにする. そして,に対する最短路が変化する.

に対して, (1–6–7–3) が最短路で長さは 3.
に対して, (5 –6–7–3) が最短路で長さは 3.

よって, 次の時点ではく. すると, 残った$r_{6}$$r_{2},$

が$r_{4},$$r_{8}$

力 $>r_{12}$ を選べる.

$r_{6},$$r_{8}$

ここでは$r_{12}$を選ひ,$r_{12}$と 2 辺 {6, 7},{7, 8} を取り除のためのパスはもうないことが分かる. このようにして, SGA が受理したリクエストの数が 12 となる.

32

3 近似よりは良くならないインスタンス

この小節では, 完全グラフ上の MEDP のインスタンスの列を構或する. このインスタンスの列|こ対すとなり, 漸近的に 3 である.
に対してる SGA の近似比は小さなであり, 3 で割り切れ$2n$の完全グラフを考える. その頂点集合は大きな に対して, 頂点数$\epsilon>0$$3-\epsilon$$V_{v}\cup V_{a}\cup V_{b}\cup V_{\mathrm{c}}$$n$て $n$ よりも少し$;|\mathrm{a}$さな数$V_{\mathrm{c}}=\{c_{1}, \ldots, c_{2k/3}\}$

$k$

を用いて,

$V_{v}=\{v_{1}, \ldots, v_{2(n-k)}\},$とする. (より明示的に書くと,$k$$V_{a}=\{a_{1}, \ldots, a_{2k/3}\},$ $V_{b}=\{b_{1}, \ldots, b_{2k/3}\}$が満たすべき条件は $3n/5\leq k\leq n$ と$\mathrm{A}\mathrm{a}$

,

う不等式を

満たすことと 3 で割り切れることである. ) リクエストの多重集合 $A=A_{v}\cup A_{a}\cup A_{b}$ UA。は次のよう t こ与
. ののサイズは $n^{2}-k^{2}$ で, すべての $i\in\{1,3,5, \ldots, 2(n-k)-1\}$ に対して\sim 2 頂点 : とえられる.
間に $2n-i$ 個のリクエストを持つ. A。のサイズは $k(n-k+1)/3$ で, すべての $i\in\{1,3,5, \ldots, 2k/3-1\}$$A_{v}$$v$$v_{*+1}$

22[こ対して,
で,2 頂点と $aj+1$ の間 [こ $n-k+1$ 個のリクエストを持つ.

$aj$

A。と同様に構成される.
$\underline{2n-\mathrm{l}\mathrm{r}\mathrm{e}\mathrm{q}.}$

図 4 がこの状況を描いている.

.

$\underline{2k+\mathrm{l}\mathrm{r}\mathrm{e}\mathrm{q}.}$$rightarrow 2n-3\mathrm{r}\mathrm{e}\mathrm{q}$$arrow$$v_{2}$$v_{1}$と A。のサイズも $k(n-k+1)/3$$A_{b}$-............

$-\theta$$v_{3}$$v_{2(n-k)-1}$$n-k+1\mathrm{r}\mathrm{e}\mathrm{q}rightarrow$.

$n-k+1\mathrm{r}\mathrm{e}\mathrm{q}rightarrow$.

$n-k+1\mathrm{r}\mathrm{e}\mathrm{q}rightarrow$$arrow$..............................

$rightarrow$$arrow$$arrow$..............................

$b_{2k/3}$$rightarrow$$arrow$$e_{2k}/3-1$$c_{3}$$c_{2}$$a_{2k}/3$$b_{2k/3-1}$$rightarrow$$rightarrow$$c_{1}$$arrow$$b_{3}$$b_{2}$$b_{1}$$a_{2k}/3-1$$rightarrow$$rightarrow$.

$arrow$$\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots$$a_{3}$$a_{2}$$a_{1}$$v_{2(n-k)}$$c_{2k}/3$

図 4: 最短路優先責欲アルゴリズムに対する悪いインスタンス.

まず, 最適解がすべてのリクエストを受理することを確かめる. どのように受理するのかを見よう. 最との間の $2n-1$ 個のリクエスト
初に, A。のリクエストを次のようにしてすべて受理する. まず,を考える. その中の 1 つを $(v_{1}-v_{2})$ を用いて受理する. その他の $2n-2$ 個のリクエストは 2 辺から成る$v_{1}$

パス $(v_{1}-u-v_{2})$ を用いて受理する.

ここで,$v_{2}$$u\in(V_{v}\backslash \{v_{1}, v_{2}\})\cup V_{a}\cup V_{b}\cup V_{\mathrm{c}}$である. これで,$v_{1}$ととの間の $2n-3$ 個のリクエストを考の間の $2n-1$ 個のリクエストをすべて受理できた. 次に,える. その中の 1 つを $(v_{3}-v_{4})$ を用いて受理する. その他の $2n-4$ 個のリクエストは 2 辺から成る\acute くスのとである. これで.
$(v_{3}-u-v_{4})$ で受理する. ここで,
$v_{4}$$v_{3}$$v_{2}$$u\in(V_{v}\backslash \{v_{1}, v_{2}, v_{3}, v_{4}\})\cup V_{a}\cup V_{b}\cup V_{\mathrm{c}}$$v_{4}$$v_{3}$, . . . と続けていく.
間の $2n-3$ 個のリクエストをすべて受理できた. このようにして,の間の $2n-2j+1$ 個のリクエストを考えるとき, その中の 1 つは辺 $(v_{2j-1}-v_{2j})$
一般的に, $v_{2j-1}$ とを用いて受理し, その他の $2n-2j$ 個のリクエストは 2 辺から成るパス $(v_{2j-1}-u-v_{2\mathrm{j}})$ を用いて受理$v_{1},$$v_{2},$$v_{3},$$v_{4},$$v_{5}$$v_{2j}$する. ここで,$u\in(V_{v}\backslash \{v_{1}, \ldots, v_{2j}\})\cup V_{a}\cup V_{b}\cup V_{\mathrm{c}}$である. こうすれば, すべての $j=1,$$\ldots,$$n-k$ この間にある $2n-2j+1$ 個のリクエストが受理できる.
と $a:+1$
2 番目に, A。のリクエストを次のように受理する. 任意の $i\in\{1,3, \ldots, 2k/3-1\}$ lr こ対して,
個は長さ
$n-k$
で受理し
,
その他の
の間にある $n-k+1$ 個のリクエストの中で, 1 つは 1 辺 $(a:-a:+1)$

おいて,$v_{2\mathrm{j}-1}$と$v_{2j}$$a_{i}$

2 のパス $(a:-u-a:+1)$ で受理する. 但し,$u\in V_{b}$とする. ここで,$k\geq 3n/5$ という条件から,

すべて

を用いて
と
と A。のリクエストはそれぞれのリクエストが受理できることが分かる. 同様に,
すべて受理できることが分かる. ゆえに, 最適解は $n^{2}+kn+k-k^{2}$ 個のリクエストすべてを受理する.
では, SGA の出力を考えよう. SGA はます長さ 1 の最短路で 個のリクエストを受理する. 次に, 長さ$A_{b}$$V_{\mathrm{c}}$$V_{a}$$n$2 の最短路で受理し始めるが, ます$a_{1}$と a2 の間に残っている $n-k$ 個のリクエストを考える. これらのリ) で受理する. 同様にして, $aj$ と$2(n-k)-1\}$ )$i\in\{1,3,$$aj+1$ の間にある $n-k$ 個のリクエストを $(aj-v:-aj+1)$ というパス (但し,クエストを$(a_{1}-v_{1}.

・a_{2})$というパス (但し,$i\in\{1,3,$ $\ldots,$ $2(n-k)-1\}$$\ldots,$で受理する. このようにして, A。のリクエスト $k(n-k+1)/3$ 個すべてを SGA は受理した. 同様にし, v、, . . ., $v_{2(n-k)-1}$ を長さ 2 のパスの中間点として用いることと A。のリクエストもて, SGA は$A_{b}$$v_{1},$ $v_{3}$ですべて受理できる.

に残っているリクエストを受理することを考える. $v_{2(n-k)-1}$ と $v_{2(n-k)}$ の間に残っている話の頂点を通るパスを使わなくてはならない. しか個のリクエストを受理するには
し, $|V_{v}\backslash \{v2(n-k)-1, v2(n-k)\}|=2(n-k-1)$ なので, 受理できるリクエストの数は $2k$ 個中 $2(n-k-1)$
個だけである. 合計して, $v_{2(n-k)-1}$ と $v_{2(n-k)}$ の間の話 +1 個のリクエストの中の $2(n-k-1)+1$ 個
だけが受理できたことになる. 次に. $v_{2(n-k)-3}$ と $v_{2(n-k)-2}$ の間 $2k+2$ 個のリクエストを見てみる. こ
では,$A_{v}$$V_{v}\backslash \{v_{2(n-k)-1}, v_{2(n-k)}\}$

23
れらのリクエストを受理するには $V_{v}\backslash \{v_{2(n-k)-3}, v_{2(n-k)-2}, v_{2(n-k)-1}, v_{2(n-k)}\}$ の頂点を通るパスを使わなくてはならない. すると, 先と同じ理由により, $2k+2$ 個中 $2(n-k-2)$ 個しか受理できないことになと間の $2k+3$ 個のリクエストの中から $2(n-k-2)+1$ 個だ } 力\leq 受理
る. 合計して,$|$$v_{2(n-k)-2}$$v_{2(n-k)-3}$

できたことになる. このようにして, 右から左に順番に行くと, 任意の $i\in\{1,3, \ldots, 2(n-k)-1\}$ に対との間の $2n-i$ 個のリクエストの中の 個しか受理できな ことになる. そして,して, SGA は$\mathrm{A}\mathrm{a}$$i$$v_{i}$$v_{i+1}$

これだけ受理し終わると, もうそれ以上受理できなくなる. よって,を受理した,

SGA は $n^{2}-kn+k$ 個のリクエストということが分かった.

$3/5\leq\alpha<1$ を満たす$\alpha$用いて,$k=\alpha n$

とおく. すると, 近似比は次のようになる.

.

$\frac{n^{2}+kn+k-2k^{2}}{n^{2}-kn+k}=\frac{n^{2}+\alpha n^{2}+\alpha n-2\alpha^{2}n^{2}}{n^{2}-\alpha n^{2}+\alpha n}nB^{arrow}\frac{1+\alpha-2\alpha^{2}}{1-\alpha}=1+2\alphaarrow 3\alphaarrow 1$

4

補足

完全グラフ上の MEDP に対して SGA が 9 近似アルゴリズムであり, また 3 近似よりは良くなれないことを示した. つまり, まだギャツプがあることになる. また, 完全グラフ上の MEDP j こ対する多項式時間
近似スキーム (polynomial-time approximation scheme) が存在する可能性さえあることも注意しておきたい. 実際, 完全グラフ上の MEDP が APX 困難であるかどうかも知られていない. (–般の無向グラフ上) より良いアルゴリズムと同じように近似不可の MEDP は APX 困難であることが知られている $[1, 4]$.

能性の方も今後の課題となる.

参考文献[1] T. Erlebach, Approximation algorithms and complexity results for path problems in trees of rings.
, ETH Ziirich, June 2001.
Report TIK-Report 109, Computer Engineering and Networks Laboratory[2] T. Erlebach and D. Vukadinovic’, New results for path problems in generalized stars, complete graphs, andgraphs. :Proceedings of the 13th International Symposium on Fundamentals of Computation
brick
Theory (FCT 2001), Lecture Notes in Computer Science 2138, 2001, 483-494.
. Johnson, Computers and $Intractab|.lity:$ A Guide to the Theory of NP-Completeness.
. Garey and[3]. Freeman and Company, New York-San Francisco, 1979.
. Vazirani and M. Yannakakis, Primal-dual approximation algorithms for integral flow and[4] N. Garg,
multicut in trees. Algorithmica I8, 1997, 3-20.
. Shepherd and M. Yannakakis, Near-Optimal hardness results[5] V. Guruswami, S. Khanna, R. Rajaraman,
and approximation algorithms for edgedisjoint paths and related problems. :Proceedings of the Slst Annual$ACM$ Syposium on Theory of Computing, 1999, 19-28.
KoIiopoulos and C. Stein, Approximating disjoint-path problems using greedy algorithms and padcing[6]lnteger
integer programs. :Integer Programming and Combinatorial Optimization, Proceedings of
Science
Computer
in
Notes
Vl,
LectureProgramming and Combinatorial Optimization Conference IPCO
1412, 1998, 153-168.
. Kleinberg, Approximation algorithms for disjoint paths problems. Ph.D. thesis, Department of Electrical[7]
Engineering and Computer Science, Massachusetts Institute of Technology, 1996.
[8] P. Kolman and C. Scheideler, Improved bounds for the unsplittable flow problem. :Proceedings of the lSth
Annual $ACM$-SIAM Symposium on Discrete Algorithm SODA 2002, 2002, 184-193.
$\mathrm{T}\mathrm{e}\mathrm{c}\mathrm{b}\dot{\mathrm{m}}\mathrm{c}\mathrm{a}1^{}$$(\mathrm{T}1\mathrm{K})$$\mathrm{l}\mathrm{n}$$\mathrm{w}\mathrm{a}\mathrm{u}$$\mathrm{M}.\mathrm{R}$$\mathrm{D}.\mathrm{S}$$\mathrm{W}.\mathrm{H}$$\mathrm{V}.\mathrm{V}$$\mathrm{F}.\mathrm{B}$$\mathrm{l}\mathrm{n}$$\mathrm{S}.\mathrm{G}.$$\mathrm{t}\mathrm{h}\epsilon 6\mathrm{t}\mathrm{h}$$\mathrm{l}\mathrm{n}$$\mathrm{J}.\mathrm{M}$$\mathrm{l}\mathrm{n}$