最小費用流問題(minimum-cost flow problem)とは、有向グラフの頂点に供給量、弧に容量と単位費用を与え、供給を需要へ容量の範囲で送る流れのうち費用の総和が最小のものを求める問題である。最大流、最短路、輸送問題、割当問題を特別な場合として含む。流れが最適であることは、残余グラフに負の閉路がないこと、また頂点のポテンシャルで被約費用をすべて非負にできることと同値である。容量と供給量が整数なら、最短路を繰り返す手順で整数の最適な流れが求まる。
前提知識: 最大流最小カット定理, Bellman–Ford法, 線形計画法
最小費用流問題(minimum-cost flow problem)は、有向グラフの各頂点に供給量と需要量を、各弧に容量と 1 単位あたりの費用を与え、供給を需要へ容量の範囲で送る流れのうち費用の総和が最小のものを求める問題である。工場から倉庫へ、倉庫から店へ品物を送る計画が典型で、最大流最小カット定理 の最大流、最短路、輸送問題、割当問題 はすべてその特別な場合になる。
この問題の中心にある事実は、流れが最適かどうかを 残余グラフ の閉路で判定できることである。最適でない流れには、流れを回すと費用が下がる閉路があり、最適な流れには、各頂点に「価格」を付けて、使える弧の費用の差がどれも非負になるようにできる。この記事では、問題と残余グラフを定義し、最適性の 3 つの言い換えが同値であること(thm-mcf-optimality)、流れが存在する条件(prop-mcf-feasible)、最短路を繰り返す手順の正しさ(thm-mcf-ssp)と、そこから従う整数性(cor-mcf-integral)を証明する。
有限の有向グラフ $G=(V,A)$ を考える。同じ向きの平行な弧があってもよく、弧 $a$ の始点を $\mathrm{t}(a)$、終点を $\mathrm{h}(a)$ と書く。頂点の集合 $S\subset V$ に対し、$S$ から出る弧の集合を $\delta^+(S)$、$S$ に入る弧の集合を $\delta^-(S)$ と書き、$\delta^\pm(\{v\})$ を $\delta^\pm(v)$ と略す。弧の関数 $x$ と弧の集合 $F$ に対して $x(F)=\sum_{a\in F}x(a)$ とする。
次のデータを考える。
$b$ を出る量から入る量を引いた差で定めたが、入る量から出る量を引いた差(需要量)で書く文献もあり、そのときは $b$ の符号が逆になる。
容量の条件だけを満たし、頂点での釣り合いを要求しない $x$($0\le x\le u$)を 前流 と呼び、
$$
e_x(v)=b(v)-x(\delta^+(v))+x(\delta^-(v))
$$
を $v$ の 残り と呼ぶ。$e_x(v)>0$ ならまだ $e_x(v)$ だけ送り出す必要があり、$e_x(v)< 0$ ならまだ $-e_x(v)$ を受け取る必要がある。前流が流れであることと、すべての $v$ で $e_x(v)=0$ であることは同じである。$\sum_v b(v)=0$ なので、いつも $\sum_v e_x(v)=0$ である。
流れの許容範囲は有界な閉集合($\mathbb R^A$ の多面体)なので、流れが 1 つでもあれば、費用の最小値は達成される。
前流 $x$ に対し、次の弧からなる有向グラフ $G_x$ を 残余グラフ という。弧 $a$($v$ から $w$ へ)ごとに
逆向きの弧 $a^-$ に沿って $\varepsilon$ を送ることは、$a$ の流れを $\varepsilon$ だけ減らすことと決める。このとき、残余グラフの弧 $\alpha$($p$ から $q$ へ)に沿って $\varepsilon$ を送ると、順向きでも逆向きでも、$p$ の残りが $\varepsilon$ 減り、$q$ の残りが $\varepsilon$ 増え、費用は $\varepsilon\,c(\alpha)$ だけ変わる。逆向きの弧の費用が $-c(a)$ なのは、流れを減らすと費用が戻るからである。
被約費用は、頂点 $v$ で品物の価格が $\pi(v)$ のとき、$p$ で買って運び $q$ で売る商売の損失 $c(\alpha)+\pi(p)-\pi(q)$ と読める。閉路 $C$ に沿って被約費用を足すと $\pi$ の項は打ち消し合うので、$\sum_{\alpha\in C}c^\pi(\alpha)=\sum_{\alpha\in C}c(\alpha)$ である。道 $P$($s$ から $t$ へ)では $\sum_{\alpha\in P}c^\pi(\alpha)=\sum_{\alpha\in P}c(\alpha)+\pi(s)-\pi(t)$ となり、$\pi$ を替えても、同じ 2 点を結ぶ道どうしの長さの順序は変わらない。これは Dijkstra法 の長さの付け替えと同じ考え方である。
| 問題 | 最小費用流としての置き方 | 最適値 |
|---|---|---|
| $s$ から $t$ への最短路(負の閉路なし) | $b(s)=1$、$b(t)=-1$、他は $0$、容量 $1$、費用は弧の長さ | 最短路の長さ |
| $s$ から $t$ への最大流 | 費用 $0$ の網に $t$ から $s$ への弧(費用 $-1$、容量は十分大)を足し、$b=0$ | 最大流の値の $-1$ 倍 |
| 輸送問題 | 工場から店への弧だけの二部グラフ、容量は十分大 | 輸送費の最小値 |
| 割当問題 | 人と仕事の二部グラフ、$b=\pm1$、容量 $1$ | 割当の費用の最小値 |
| 循環 | すべての $b(v)=0$ | 閉路に沿って回す費用の最小値 |
最大流の置き方では、$t$ から $s$ への弧に 1 単位流すごとに費用が $1$ 下がるので、費用の最小化は $s$ から $t$ へ流せる量の最大化と同じになる。「容量は十分大」は、弧の容量の総和などの有限の値で足りる。最短路の置き方で負の閉路がないと、容量 1 の最適な整数の流れは、$s$ から $t$ への道 1 本と、費用 $0$ の閉路に分かれる(流れの閉路への分解は ネットワークフロー の記事にある)。
流れ $x$ について、次は同値である。
(1)⇒(2) $G_x$ に費用の和が負の有向閉路があるとする。負の閉路を含む閉じた歩道は、同じ頂点で切り分けると単純な閉路の和になり、そのどれかの費用は負なので、単純な閉路 $C$ で $\sum_{\alpha\in C}c(\alpha)< 0$ のものがとれる。$C$ の弧の残りの容量の最小値を $\varepsilon>0$ とし、$C$ の各弧に沿って $\varepsilon$ を送る。
$C$ が同じ $a$ の $a^+$ と $a^-$ を両方含むのは $C$ がこの 2 本だけの閉路のときで、その費用は $c(a)-c(a)=0$ なので負ではない。したがって $C$ の弧はすべて異なる元の弧から来ており、送ったあとも $0\le x\le u$ が保たれる。$C$ の各頂点では、入る弧と出る弧が 1 本ずつなので、残りは $\varepsilon$ 増えて $\varepsilon$ 減り、変わらない。よって送ったあとも流れで、費用は $\varepsilon\sum_{\alpha\in C}c(\alpha)< 0$ だけ変わる。$x$ より費用の小さい流れがあるので、$x$ は最小でない。
(2)⇒(3) $G_x$ に新しい頂点 $r$ と、$r$ から各頂点 $v$ への費用 $0$ の弧を足したグラフ $H$ を考える。$r$ に入る弧はないので、$H$ の有向閉路は $G_x$ の有向閉路であり、仮定から費用は負でない。負の閉路がない有限の有向グラフでは、$r$ から到達できる各頂点への最短の歩道の長さ(距離)が有限の値で定まる(Bellman–Ford法 の記事の距離が定まる条件)。$\pi(v)$ を $H$ での $r$ から $v$ への距離とする。$r$ から $v$ への弧があるので、すべての $v$ で $\pi(v)$ は有限である。$G_x$ の弧 $\alpha$($p$ から $q$ へ)について、$r$ から $p$ への最短の歩道に $\alpha$ をつなげると $q$ への歩道になるので
$$
\pi(q)\le\pi(p)+c(\alpha),\qquad\text{すなわち}\qquad c^\pi(\alpha)\ge 0
$$
である。
(3)⇒(1) $y$ を任意の流れとする。弧 $a$ に対し、元のグラフでの被約費用を $c^\pi(a)=c(a)+\pi(\mathrm t(a))-\pi(\mathrm h(a))$ と書く。$x$ と $y$ はどちらも各頂点で出る量と入る量の差が $b(v)$ なので
$$
\sum_{a\in A}\bigl(\pi(\mathrm t(a))-\pi(\mathrm h(a))\bigr)\bigl(y(a)-x(a)\bigr)=\sum_{v\in V}\pi(v)\Bigl(\bigl(y(\delta^+(v))-y(\delta^-(v))\bigr)-\bigl(x(\delta^+(v))-x(\delta^-(v))\bigr)\Bigr)=\sum_{v\in V}\pi(v)\bigl(b(v)-b(v)\bigr)=0
$$
である。左辺の和を弧ごとに頂点へ振り分けると、$\pi(v)$ の係数が $v$ から出る量の差から入る量の差を引いたものになるからである。したがって
$$
c(y)-c(x)=\sum_{a\in A}c^\pi(a)\bigl(y(a)-x(a)\bigr)
$$
となる。各項が非負であることを示す。$y(a)>x(a)$ なら $x(a)< y(a)\le u(a)$ なので $a^+$ が $G_x$ にあり、$c^\pi(a^+)=c^\pi(a)\ge 0$ である。$y(a)< x(a)$ なら $x(a)>0$ なので $a^-$ が $G_x$ にあり、$c^\pi(a^-)=-c(a)+\pi(\mathrm h(a))-\pi(\mathrm t(a))=-c^\pi(a)\ge 0$、すなわち $c^\pi(a)\le 0$ である。どちらの場合も $c^\pi(a)(y(a)-x(a))\ge 0$ で、$y(a)=x(a)$ なら項は $0$ である。よって $c(y)\ge c(x)$ で、$x$ は最小である。
条件 3 は 線形計画法 の言葉では相補性条件である。最小費用流問題を線形計画として書くと、各頂点の釣り合いの式に双対変数 $\pi(v)$ が対応し、「流れを増やせる弧の被約費用は非負、減らせる弧の被約費用は非正」が双対の実行可能性と相補性の組になる。
流れが存在するための必要十分条件は、すべての $S\subset V$ について
$$
b(S)\le u(\delta^+(S))
$$
が成り立つことである。ここで $b(S)=\sum_{v\in S}b(v)$ とする。
必要性 流れ $x$ があれば、$S$ の頂点について釣り合いの式を足すと、両端が $S$ にある弧の項は打ち消し合い
$$
b(S)=x(\delta^+(S))-x(\delta^-(S))\le u(\delta^+(S))-0
$$
となる。
十分性 新しい頂点 $s^*$、$t^*$ を足し、$b(v)>0$ の頂点 $v$ には $s^*$ から $v$ への容量 $b(v)$ の弧を、$b(v)< 0$ の頂点 $v$ には $v$ から $t^*$ への容量 $-b(v)$ の弧を加えたネットワーク $N$ を作る。$B=\sum_{b(v)>0}b(v)$ とおく。$N$ で $s^*$ から $t^*$ への値 $B$ の流れがあれば、それは $s^*$ から出る弧と $t^*$ に入る弧をすべて満たしているので、元の弧への制限は各頂点で出る量と入る量の差が $b(v)$ の流れである。
$N$ の $s^*$-$t^*$ カットは $S\subset V$ を使って $\{s^*\}\cup S$ と書ける。その容量は、$S$ の外の供給の頂点への弧、$S$ から出る元の弧、$S$ の中の需要の頂点から $t^*$ への弧の容量の和で
$$
\sum_{v\notin S,\ b(v)>0}b(v)+u(\delta^+(S))+\sum_{v\in S,\ b(v)< 0}\bigl(-b(v)\bigr)=B-b(S)+u(\delta^+(S))\ge B
$$
となる。等号の部分は $B=\sum_{b(v)>0}b(v)$ を $S$ の中と外に分ければ分かる。$S=\emptyset$ のカットの容量はちょうど $B$ なので、最小カットの容量は $B$ である。最大流最小カット定理 により、値 $B$ の流れがある。
この条件は、どの頂点の集合 $S$ についても「$S$ の中の正味の供給を、$S$ から出る弧で運び出せる」ということである。条件が成り立たない $S$ は、流れがないことの証拠になる。thm-mcf-ssp の手順は、流れがないときにそのような $S$ を見つける。
thm-mcf-optimality の条件 3 を保ったまま、残りを最短路に沿って少しずつ解消していくのが次の手順である。
最短路の繰り返し:容量 $u$ と供給量 $b$ は整数とする。
容量 $u$ と供給量 $b$ が整数で、費用 $c$ は任意の実数とする。上の手順は有限回で止まり、次が成り立つ。
手順 1 の直後 $x(a)< u(a)$ の弧は $c(a)\ge 0$ なので $c^0(a^+)=c(a)\ge 0$ である。$x(a)>0$ の弧は $x(a)=u(a)$ かつ $c(a)< 0$ なので $c^0(a^-)=-c(a)>0$ である。
1 回の繰り返しで不変量が保たれること 手順 3 の時点で $c^\pi\ge 0$ とする。長さが非負なので、距離 $d$ は Dijkstra法 で求められ、$G_x$ の各弧 $\alpha$($p$ から $q$ へ)で $d(q)\le d(p)+c^\pi(\alpha)$ が成り立つ。$d'(v)=\min(d(v),D)$ とおくと
$$
d'(q)\le d'(p)+c^\pi(\alpha)
$$
も成り立つ。実際、$d(p)\ge D$ なら $d'(p)=D$ で $d'(q)\le D\le D+c^\pi(\alpha)$、$d(p)< D$ なら $d'(q)\le d(q)\le d(p)+c^\pi(\alpha)=d'(p)+c^\pi(\alpha)$ である。新しいポテンシャル $\pi'=\pi+d'$ では $c^{\pi'}(\alpha)=c^\pi(\alpha)+d'(p)-d'(q)\ge 0$ である。
$P$ の上の頂点 $v$ では、$P$ の $v$ までの部分も最短路なので $d(v)\le D$、$d'(v)=d(v)$ で、$P$ の各弧 $\alpha$ で $d(q)=d(p)+c^\pi(\alpha)$、すなわち $c^{\pi'}(\alpha)=0$ である。$P$ に沿って送ると、新しく残余グラフに現れうる弧は $P$ の弧の逆向きだけで、その被約費用は $-c^{\pi'}(\alpha)=0$ である。消える弧は条件に影響しない。よって送ったあとの $G_x$ でも $c^{\pi'}\ge 0$ である。
$\delta$ は整数どうしの最小値で、$s\in S^+$、$t\in S^-$ と残りの容量の正であることから $\delta\ge 1$ である。$x$ は整数のまま更新される。$s$ の残りは $\delta$ 減り、$t$ の残りは $\delta$ 増え、途中の頂点の残りは変わらないので、残りの正の部分の和は $\delta\ge1$ ずつ減る。したがって手順は有限回で止まり、回数の上限が成り立つ。
手順 2 で止まったとき $x$ は流れで、$c^\pi\ge 0$ なので thm-mcf-optimality の 3⇒1 により最小である。
手順 4 で止まったとき $R$ は $S^+$ を含み、$S^-$ と交わらない。$R$ から出る元の弧 $a$ では $a^+$ が $G_x$ にないので $x(a)=u(a)$、$R$ に入る元の弧 $a$ では $R$ の中から外へ向かう $a^-$ がないので $x(a)=0$ である。よって
$$
\sum_{v\in R}e_x(v)=b(R)-x(\delta^+(R))+x(\delta^-(R))=b(R)-u(\delta^+(R))
$$
である。左辺は正の残りをもつ頂点をすべて含み負の残りの頂点を含まない和なので正である。したがって $b(R)>u(\delta^+(R))$ で、prop-mcf-feasible の必要性から流れはない。
容量 $u$ と供給量 $b$ が整数で、流れが 1 つでもあれば、費用 $c$ が実数でも、整数値の最小費用の流れがある。
流れがあるので、thm-mcf-ssp の 3 により手順は手順 4 では止まらず、手順 2 で整数値の最小費用の流れを出力する。
費用 $c$ に整数性は要らない。同じ結論は、流れの制約の係数行列(接続行列)が 完全単模行列 であることからも従う。そちらは線形計画の頂点がすべて整数であるという形の主張で、線形計画法 の単体法の出す最適解が整数になることも分かる。
手順 3 で距離を求めるのに Dijkstra法 が使えるのは、被約費用が非負だからである。元の費用 $c$ のままでは、逆向きの弧が負の費用をもつので Dijkstra 法は使えない。ポテンシャルの役割は、Bellman–Ford法 を 1 回だけ(ここでは手順 1 の工夫で 0 回)使ったあと、残りをすべて Dijkstra 法で済ませることにある。
別の手順として、流れを 1 つ求めておき(prop-mcf-feasible の証明の最大流で求まる)、$G_x$ に負の閉路がある限り thm-mcf-optimality の 1⇒2 の証明のとおりに閉路に沿って送る方法がある。負の閉路は Bellman–Ford法 で見つけられる。$u$・$b$・$c$ が整数なら、最初の流れを整数にとれて送る量 $\varepsilon$ も $1$ 以上の整数になるので、1 回ごとに費用は $1$ 以上下がり、費用は $\sum_a\min(c(a),0)u(a)$ 以上なので有限回で止まり、止まったときは条件 2 から最適である。ただし閉路の選び方によっては回数が非常に多くなりうる。
小さい網を手で解くときは、次の順に進める。
頂点 $s,a,b,t$ と次の弧(容量, 費用)を考え、$b(s)=4$、$b(t)=-4$、$b(a)=b(b)=0$ とする。
| 弧 | $s\to a$ | $s\to b$ | $a\to b$ | $a\to t$ | $b\to t$ |
|---|---|---|---|---|---|
| 容量 | 3 | 2 | 2 | 2 | 3 |
| 費用 | 1 | 4 | 1 | 6 | 1 |
費用が負の弧はないので $x=0$、$\pi=0$ から始める。各回の距離 $d$(順に $s,a,b,t$)、選んだ道、送る量は次のとおりである。
| 回 | $d$ | 道(元の費用) | 送る量 | 更新後の $\pi$ |
|---|---|---|---|---|
| 1 | $(0,1,2,3)$ | $s\,a\,b\,t$(3) | 2 | $(0,1,2,3)$ |
| 2 | $(0,0,2,2)$ | $s\,b\,t$(5) | 1 | $(0,1,4,5)$ |
| 3 | $(0,0,0,2)$ | $s\,a\,t$(7) | 1 | $(0,1,4,7)$ |
1 回目は $a\to b$ の容量 2 で、2 回目は $b\to t$ の残り 1 で量が決まる。道の費用は $3,5,7$ と増えていき、総費用は $2\cdot 3+1\cdot 5+1\cdot 7=18$ である。最後の流れは $x(s\to a)=3$、$x(s\to b)=1$、$x(a\to b)=2$、$x(a\to t)=1$、$x(b\to t)=3$ である。
最適性は $\pi=(0,1,4,7)$ で確かめられる。残余の弧は、$a\to s$(被約費用 $0$)、$s\to b$ と $b\to s$($0$)、$b\to a$($2$)、$a\to t$ と $t\to a$($0$)、$t\to b$($2$)で、どれも非負である。
供給を $b(s)=5$、$b(t)=-5$ に増やしても流れはあり、4 回目の道は逆向きの弧 $b\to a$ を通る $s\,b\,a\,t$(費用 $4-1+6=9$)で、総費用は $27$ になる。$6$ にすると、$t$ に入る弧の容量の和が $5$ なので、$S=\{s,a,b\}$ で $b(S)=6>5=u(\delta^+(S))$ となり流れはない。手順は 4 回送ったあと残り $1$ を運べずに止まる。このとき $s$ から出る 2 本の弧は満たされているので、出力は $R=\{s\}$ で、$b(R)=6>5=u(\delta^+(R))$ である。条件を満たさない集合は 1 つとは限らない。
頂点 $s,a,b,t$ で、すべての弧の容量を $1$ とし、費用を $s\to a$、$a\to b$、$b\to t$ は $1$、$s\to b$、$a\to t$ は $3$ とする。$b(s)=2$、$b(t)=-2$ とする。
1 回目の最短路は $s\,a\,b\,t$(費用 3)で、1 単位送る。このあと $s$ から出る使える弧は $s\to b$ だけで、$b$ から先の $b\to t$ は満たされている。元の向きの弧だけでは $t$ に届かない。
残余グラフには逆向きの弧 $b\to a$(費用 $-1$)があり、2 回目の最短路は $s\,b\,a\,t$(費用 $3-1+3=5$)になる。これに 1 単位送ると $a\to b$ の流れは $0$ に戻り、結果は $s\,a\,t$ と $s\,b\,t$ に 1 単位ずつ(費用 $4+4=8$)で、これが最小である。1 回目に選んだ道の一部が、2 回目に取り消されている。
ex-mcf-trace の網で費用をすべて $0$ にし、$t$ から $s$ への弧(容量 $6$、費用 $-1$)を足して、すべての $b(v)=0$ とする。最小費用は $-5$ で、$s$ から $t$ への最大流の値は $5$ である。$t$ に入る弧の容量の和が $5$ なので、これ以上は流せない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 手順 1 で負の費用の弧を満たす | 弧 $s\to t$(容量 1、費用 1)と、別の 2 頂点の弧 $p\to q$(容量 1、費用 $-2$)、$q\to p$(容量 1、費用 0)、$b(s)=1$、$b(t)=-1$。$x=0$、$\pi=0$ から始めると $s\to t$ に送って費用 $1$ で止まる | 出力が最小でない。最小は $p\,q\,p$ を回した費用 $-1$ で、$x=0$ では $c^0(p\to q)=-2< 0$ |
| 容量 $u$ が整数 | 平行な 2 本の弧 $s\to t$(容量 $\frac12$ ずつ、費用 0)、$b(s)=1$、$b(t)=-1$ | 流れは $(\frac12,\frac12)$ だけで、整数の流れがない(cor-mcf-integral) |
| 供給量 $b$ が整数 | 弧 $s\to t$(容量 1、費用 1)、$b(s)=\frac12$、$b(t)=-\frac12$ | 流れは $x=\frac12$ だけで、整数の流れがない |
| 容量が有限 | 弧 $p\to q$(費用 $-1$)と $q\to p$(費用 $0$)の容量を無限大にし、$b=0$ | $p\,q\,p$ を $k$ 回まわすと費用 $-k$ で、最小値がない |
| 残余グラフに逆向きの弧を入れる | ex-mcf-backward | 1 回目のあと $t$ に届かず「流れなし」と誤って止まる |
最適性の判定(thm-mcf-optimality)は容量や供給量の整数性を使っておらず、実数のデータでそのまま成り立つ。整数性が要るのは、手順が有限回で止まることと、整数の最適解の存在である。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 逆向きの弧の費用も $c(a)$ | $-c(a)$ | 流れを減らすと費用は戻る(def-mcf-residual) |
| 安い道から順に流せば最適で、流した量は変えない | 前に流した量を逆向きの弧で取り消すことがある | ex-mcf-backward |
| 残余グラフでも元の費用のまま Dijkstra 法を使う | 被約費用 $c^\pi$ で使う | 逆向きの弧は負の費用をもつ |
| 届かない頂点のポテンシャルは更新しなくてよい | $D$ を足す($\min(d,D)$ で $d=\infty$ なら $D$) | 届かない頂点から届く頂点への弧の被約費用が負になりうる |
| 費用が整数でないと整数の最適解はない | 容量と供給量が整数なら十分 | cor-mcf-integral |
| 元のグラフに負の閉路がなければ $x=0$ から始めてよい | 負の費用の弧があれば満たしてから始めるか、最初のポテンシャルを Bellman–Ford法 で求める | 不変量 $c^\pi\ge 0$ が最初に要る |
最後の行の後半は、元のグラフに負の閉路がなければ、$x=0$ のまま、元のグラフでの距離を最初のポテンシャルにしてもよいということである(thm-mcf-optimality の 2⇒3 の証明と同じ作り方)。
最小費用流の一般の模型と、輸送問題・割当問題・最大流($t$ から $s$ への弧を足す置き方)・最短路をその特別な場合として書く方法は BHM77 §8.1–8.2(pp. 227–234)に、整数性(Integrality Property)は同書 §8.7(p. 254)にある。流れの制約の行列が完全単模であること(Theorem 8.6)と、そこから従う整数性(Corollary 8.7)は Lee21 p. 97 にあり、模型の書き方は同書 §2.3(p. 12)にある。ポテンシャルで長さを付け替えて負の長さを消す考え方は Eri19 §9.3–9.4(pp. 311–312)にある。thm-mcf-optimality、prop-mcf-feasible、thm-mcf-ssp の証明はこの記事で書き下した。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する