コンピュータサイエンス と オペレーションズリサーチ では 、 ランダム化丸め [1]は 近似アルゴリズムの
設計と分析に広く使用されているアプローチです 。 [2] [3]
多くの 組み合わせ最適化 問題は、計算上、正確に（最適に）解くことが 困難 です。このような問題では、ランダム化された丸めを使用して、高速（ 多項式時間 ） 近似アルゴリズム 、つまり、任意の入力に対してほぼ最適なソリューションを返すことが保証されているアルゴリズムを設計できます。
ランダム化丸めの基本的な考え方は、問題の緩和 の最適解を 元の問題の近似最適解に変換することです。結果として得られるアルゴリズムは通常、 確率的方法 を使用して分析されます。
概要 基本的なアプローチには 3 つのステップがあります。
解決すべき問題を 整数線形計画法 (ILP) として定式化します。 ILP の 線形計画緩和 (LP)に対する 最適な分数解を計算します。
x
{\displaystyle x}
LP の 分数解を ILP の整数解に丸めます。
x
{\displaystyle x}
x ′
{\displaystyle x'}
(このアプローチは線形計画法で最も一般的に適用されますが、他の種類の緩和法が使用されることもあります。たとえば、Goemans と Williamson の 半正定値計画法 に基づく
Max-Cut 近似アルゴリズムを参照し てください。)
最初のステップでは、適切な整数線形計画法を選択することが課題となります。線形計画法、特に線形計画法と整数線形計画法を使用したモデリングに精通している必要があります。多くの問題では、以下の Set Cover の例のように、適切に機能する自然な整数線形計画法が存在します。(整数線形計画法には小さな
整数ギャップ が必要です。実際、整数ギャップの境界を証明するためにランダムな丸めがよく使用されます。)
2 番目のステップでは、通常、標準的な 線形計画アルゴリズムを使用して、最適な分数解を 多項式時間 で計算できます 。
3 番目のステップでは、分数解を整数解に変換する必要があります (つまり、元の問題の解になります)。これは、分数解の 丸めと 呼ばれます。結果として得られる整数解のコストは、分数解のコストより大幅に高くならないはずです (証明可能)。これにより、整数解のコストが最適な整数解のコストより大幅に高くならないことが保証されます。
3 番目のステップ (丸め) を実行するために使用される主な手法は、ランダム化を使用し、次に確率論的議論を使用して丸めによるコストの増加を制限することです (組み合わせ論の 確率論的方法 に従います)。その中で、確率論的議論は、望ましい特性を持つ離散構造の存在を示すために使用されます。このコンテキストでは、このような議論を使用して次のことを示します。
LP の 任意の分数解が与えられた場合
x
{\displaystyle x}
x ′
{\displaystyle x'}
x
{\displaystyle x}
、ランダム化された丸めプロセスにより、正の確率で、何らかの望ましい基準に従って 近似する整数解が生成されます。 最後に、3 番目のステップを計算的に効率的にするには、 が高確率で 近似することを示すか
(ステップがランダム化を維持できるようにするため) 、通常は 条件付き確率法を 使用して丸めステップを 非ランダム化し ます。後者の方法は、ランダム化された丸めプロセスを、良好な結果に到達することが保証された効率的な決定論的プロセスに変換します。
x ′
{\displaystyle x'}
x
{\displaystyle x}
例: 集合被覆問題 次の例は、ランダム化された丸めを使用して、集合被覆問題 の近似アルゴリズムを設計する方法を示しています。 宇宙上の集合被覆の 任意のインスタンスを固定します 。
⟨ c 、
S
⟩
{\displaystyle \langle c,{\mathcal {S}}\rangle }
あなた
{\displaystyle {\mathcal {U}}}
分数解の計算 ステップ 1 では、 このインスタンスの
集合被覆の標準整数線形計画 を IP とします。
ステップ2 では 、LPをIPの 線形計画緩和 とし、 任意の標準 線形計画 アルゴリズムを使用してLPの最適解を計算します。これには、入力サイズの多項式の時間がかかります。LPの実行可能な解は、 各セットに 非負の重みを割り当てるベクトルで あり、各要素について 、を含むセットに 割り当て られる合計重みが 少なくとも1である、つまり、
x
∗
{\displaystyle x^{*}}
x
{\displaystyle x}
s ∈
S
{\displaystyle s\in {\mathcal {S}}}
x
s
{\displaystyle x_{s}}
e ∈
あなた
{\displaystyle e\in {\mathcal {U}}}
x ′
{\displaystyle x'}
e
{\displaystyle e}
e
{\displaystyle e}
∑
s ∋ e
x
s
≥ 1.
{\displaystyle \sum _{s\ni e}x_{s}\geq 1.}
最適解 とは、コストが
x
∗
{\displaystyle x^{*}}
∑
s ∈
S
c （ S ）
x
s
∗
{\displaystyle \sum _{s\in {\mathcal {S}}}c(S)x_{s}^{*}}
は可能な限り小さくなります。 の任意の集合被覆は 実行可能な解を与えることに注意してください （ の場合 は 、 それ以外の場合は ）。 これのコストは のコストに等しく 、つまり、
Ｃ
{\displaystyle {\mathcal {C}}}
S
{\displaystyle {\mathcal {S}}}
x
{\displaystyle x}
x
s
= 1
{\displaystyle x_{s}=1}
s ∈
Ｃ
{\displaystyle s\in {\mathcal {C}}}
x
s
= 0
{\displaystyle x_{s}=0}
Ｃ
{\displaystyle {\mathcal {C}}}
x
{\displaystyle x}
∑
s ∈
Ｃ
c （ s ） =
∑
s ∈
S
c （ s ）
x
s
。
{\displaystyle \sum _{s\in {\mathcal {C}}}c(s)=\sum _{s\in {\mathcal {S}}}c(s)x_{s}.}
言い換えれば、線形計画 LP は、 与えられた集合被覆問題の
緩和です。
は LP の実行可能解の中でコストが最小である ため、 のコストは 最適集合カバーのコストの下限となります 。
x
∗
{\displaystyle x^{*}}
x
∗
{\displaystyle x^{*}}
ランダム丸めステップ ステップ 3 では 、最小コストの分数集合カバー を、実行可能な整数ソリューション (真の集合カバーに対応) に変換する必要があります。丸め手順 により、正の確率で、コストが のコストの小さな係数以内になる が生成されます 。その後 ( のコストは 最適集合カバーのコストの下限であるため)、 のコストは 最適コストの小さな係数以内になります。
x
∗
{\displaystyle x^{*}}
x ′
{\displaystyle x'}
x ′
{\displaystyle x'}
x
∗
{\displaystyle x^{*}}
x
∗
{\displaystyle x^{*}}
x ′
{\displaystyle x'}
出発点として、最も自然な丸め方式を検討してください。
各セットについて 、 の 確率でを取り 、それ以外の場合は を取ります 。
s ∈
S
{\displaystyle s\in {\mathcal {S}}}
x
s
′
= 1
{\displaystyle x'_{s}=1}
分 （ 1 、
x
s
∗
）
{\displaystyle \min(1,x_{s}^{*})}
x
s
′
= 0
{\displaystyle x'_{s}=0}
この丸め方式では、選択されたセットの期待コストは最大で 、部分カバーのコストになります。これは良いことです。残念ながら、カバー率は良くありません。変数 が小さい場合、要素がカバーされない確率 は約
∑
s
c （ s ）
x
s
∗
{\displaystyle \sum _{s}c(s)x_{s}^{*}}
x
s
∗
{\displaystyle x_{s}^{*}}
e
{\displaystyle e}
∏
s ∋ e
1 −
x
s
∗
≈
∏
s ∋ e
経験 （ −
x
s
∗
） = 経験
（
−
∑
s ∋ e
x
s
∗
）
≈ 経験 （ − 1 ） 。
{\displaystyle \prod _{s\ni e}1-x_{s}^{*}\approx \prod _{s\ni e}\exp(-x_{s}^{*})=\exp {\Big (}-\sum _{s\ni e}x_{s}^{*}{\Big )}\approx \exp(-1).}
したがって、期待される範囲では要素の一定の割合のみがカバーされます。
すべての要素を高い確率でカバーするために 、標準的な丸め方式では、まず 適切な係数で丸め確率 をスケールアップします 。標準的な丸め方式は次のとおりです。
x ′
{\displaystyle x'}
λ > 1
{\displaystyle \lambda >1}
パラメータを固定します 。各セット ごとに、
λ ≥ 1
{\displaystyle \lambda \geq 1}
s ∈
S
{\displaystyle s\in {\mathcal {S}}}
確率で を 取り 、そうでない場合は を取ります 。
x
s
′
= 1
{\displaystyle x'_{s}=1}
分 （ λ
x
s
∗
、 1 ）
{\displaystyle \min(\lambda x_{s}^{*},1)}
x
s
′
= 0
{\displaystyle x'_{s}=0}
確率を だけ大きくすると、 期待コストは だけ増加します が、すべての要素がカバーされる可能性が高くなります。アイデアは、 すべての要素が非ゼロの確率でカバーされることが証明されるように、できるだけ小さいものを選択することです。詳細な分析は次のとおりです。
λ
{\displaystyle \lambda}
λ
{\displaystyle \lambda}
λ
{\displaystyle \lambda}
補題（丸め方式の近似保証） 修正します 。正の確率で、丸め方式は 最大でコストのセットカバーを返します （したがって、コスト× 最適セットカバーのコストになります）。
λ = 行 （ 2
|
あなた
|
）
{\displaystyle \lambda =\ln(2|{\mathcal {U}}|)}
x ′
{\displaystyle x'}
2 行 （ 2
|
あなた
|
） c ⋅
x
∗
{\displaystyle 2\ln(2|{\mathcal {U}}|)c\cdot x^{*}}
お （ ログ
|
あなた
|
）
{\displaystyle O(\log |{\mathcal {U}}|)}
(注意: を注意深く計算すると に減らすことができます 。)
お （ ログ
|
あなた
|
）
{\displaystyle O(\log |{\mathcal {U}}|)}
行 （
|
あなた
|
） + お （ ログ ログ
|
あなた
|
）
{\displaystyle \ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)}
証拠 ランダム丸め方式の出力は 、次の「悪い」イベントが発生しない限り、望ましい特性を持ちます。
x ′
{\displaystyle x'}
の コストが を超える 、または
c ⋅
x ′
{\displaystyle c\cdot x'}
x ′
{\displaystyle x'}
2 λ c ⋅
x
∗
{\displaystyle 2\lambda c\cdot x^{*}}
いくつかの要素については 、 をカバーできません 。
e
{\displaystyle e}
x ′
{\displaystyle x'}
e
{\displaystyle e}
それぞれの期待値 は最大 です 。 期待値の線形性 により、 の期待値は
最大 です 。したがって、 マルコフの不等式 により、上記の最初の悪いイベントの確率は最大 です 。
x
s
′
{\displaystyle x'_{s}}
λ
x
s
∗
{\displaystyle \lambda x_{s}^{*}}
c ⋅
x ′
{\displaystyle c\cdot x'}
∑
s
c （ s ） λ
x
s
∗
= λ c ⋅
x
∗
{\displaystyle \sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}}
1
/
2
{\displaystyle 1/2}
残りの悪いイベント（各要素 につき1つ ）については、 任意の要素 について、 がカバーされない
確率は
e
{\displaystyle e}
∑
s ∋ e
x
s
∗
≥ 1
{\displaystyle \sum _{s\ni e}x_{s}^{*}\geq 1}
e
{\displaystyle e}
e
{\displaystyle e}
∏
s ∋ e
（
1 − 分 （ λ
x
s
∗
、 1 ）
）
<
∏
s ∋ e
経験 （
−
λ
x
s
∗
） = 経験
（
−
λ
∑
s ∋ e
x
s
∗
）
≤ 経験 （
−
λ ） = 1
/
（ 2
|
あなた
|
） 。
{\displaystyle {\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s}^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{aligned}}}
(これは不等式 を使用しますが 、これは に対して厳密です 。)
1
+
z
≤
e
z
{\displaystyle 1+z\leq e^{z}}
z
≠
0
{\displaystyle z\neq 0}
したがって、各要素について 、要素がカバーされない確率は 未満です 。
|
U
|
{\displaystyle |{\mathcal {U}}|}
1
/
(
2
U
)
{\displaystyle 1/(2{\mathcal {U}})}
和集合の境界 により 、 悪いイベントの 1 つが発生する確率は より小さくなります 。したがって、確率が正の場合、悪いイベントは発生せず、 は コストが最大 の集合被覆となります 。QED
1
+
|
U
|
{\displaystyle 1+|{\mathcal {U}}|}
1
/
2
+
|
U
|
/
(
2
U
)
=
1
{\displaystyle 1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1}
x
′
{\displaystyle x'}
2
λ
c
⋅
x
∗
{\displaystyle 2\lambda c\cdot x^{*}}
条件付き確率法を用いた非ランダム化 上記の補題は、 コスト ) の集合被覆の 存在を 示しています。この文脈では、私たちの目標は存在証明だけではなく、効率的な近似アルゴリズムであるため、まだ完了していません。
O
(
log
(
|
U
|
)
c
⋅
x
∗
{\displaystyle O(\log(|{\mathcal {U}}|)c\cdot x^{*}}
1 つのアプローチ
としては、少しだけ増加させて、成功の確率が少なくとも 1/4 であることを示すことが考えられます。この変更により、ランダムな丸め手順を数回繰り返すだけで、高い確率で成功の結果を確実に得ることができます。
λ
{\displaystyle \lambda }
このアプローチは近似比を弱めます。次に、上記の存在証明の近似比と一致することが保証された決定論的アルゴリズムを生成する別のアプローチについて説明します。このアプローチは 条件付き確率法 と呼ばれます。
決定論的アルゴリズムは、ランダムな丸め方式をエミュレートします。つまり、各セットを 順番に検討し、 を選択します。ただし、 に基づいて各選択を ランダムに 行うのではなく、これまでの選択を考慮して、失敗の条件付き確率を 1 未満に保つ ように
、 決定論的に 選択し ます 。
s
∈
S
{\displaystyle s\in {\mathcal {S}}}
x
s
′
∈
{
0
,
1
}
{\displaystyle x'_{s}\in \{0,1\}}
x
∗
{\displaystyle x^{*}}
条件付き失敗確率の制限 条件付き失敗確率を1未満に保つために、各変数を順番に設定できるようにしたい 。これを行うには、条件付き失敗確率の適切な境界が必要である。境界は、元の存在証明を改良することによって得られる。その証明は、確率変数の期待値によって暗黙的に失敗確率を制限している。
x
s
′
{\displaystyle x'_{s}}
F
=
c
⋅
x
′
2
λ
c
⋅
x
∗
+
|
U
(
m
)
|
{\displaystyle F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|}
、 どこ
U
(
m
)
=
{
e
:
∏
s
∋
e
(
1
−
x
s
′
)
=
1
}
{\displaystyle {\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \}}}
最後にカバーされなかった要素の集合です。
ランダム変数は 少し神秘的に見えるかもしれませんが、それは確率的証明を体系的に反映しています。 の最初の項は、 マルコフの不等式 を適用して
最初の悪いイベント（コストが高すぎる）の確率を制限する ことから来ています。 のコストが高すぎる場合、少なくとも 1 に寄与します。 2 番目の項は、第 2 種類の悪いイベント（カバーされていない要素）の数を数えます。 にカバーされていない要素が 1 つでもある 場合、 少なくとも 1 に寄与します。したがって、 が 1 未満の
結果では、 はすべての要素をカバーし、コストが補題から必要な制限を満たす必要があります。つまり、丸めステップが失敗すると、 になります 。これは、（ マルコフの不等式 より） が
失敗の確率の上限であることを意味します。
上記の議論は補題の証明にすでに暗黙的に含まれていることに注意してください。補題は、計算によって であることも示しています 。
F
{\displaystyle F}
F
{\displaystyle F}
F
{\displaystyle F}
x
′
{\displaystyle x'}
F
{\displaystyle F}
x
′
{\displaystyle x'}
F
{\displaystyle F}
x
′
{\displaystyle x'}
F
≥
1
{\displaystyle F\geq 1}
E
[
F
]
{\displaystyle E[F]}
E
[
F
]
<
1
{\displaystyle E[F]<1}
条件付き確率法を適用するには、丸めステップが進むにつれて 条件付き 失敗確率を制限するように議論を拡張する必要があります。通常、これは体系的な方法で行うことができますが、技術的には面倒な場合があります。
では、 丸めステップがセットを反復するときの 条件 付き失敗確率はどうなるでしょうか?丸めステップが失敗する結果では、 マルコフの不等式 により、 条件 付き失敗確率は最大で の 条件付き 期待値になります 。
F
≥
1
{\displaystyle F\geq 1}
F
{\displaystyle F}
次に、元の証明で の 無条件期待値を計算 したのと同じように、 の条件付き期待値を計算します。ある反復 の終了時の丸め処理の状態を考えます 。 が、 これまでに検討したセット（ の最初のセット ）を表すものとします。 が（部分的に割り当てられた）ベクトルを表すものと します（したがって、 の場合にのみ決定されます ）
。 各セット について 、 が 1 に設定される
確率を表すものとします 。 がまだカバーされていない要素を含むものとします。すると、 の条件付き期待値は 、これまでの選択、つまり が与えられた場合 、次のようになります。
F
{\displaystyle F}
F
{\displaystyle F}
t
{\displaystyle t}
S
(
t
)
{\displaystyle S^{(t)}}
t
{\displaystyle t}
S
{\displaystyle {\mathcal {S}}}
x
(
t
)
{\displaystyle x^{(t)}}
x
′
{\displaystyle x'}
x
s
(
t
)
{\displaystyle x_{s}^{(t)}}
s
∈
S
(
t
)
{\displaystyle s\in S^{(t)}}
s
∉
S
(
t
)
{\displaystyle s\not \in S^{(t)}}
p
s
=
min
(
λ
x
s
∗
,
1
)
{\displaystyle p_{s}=\min(\lambda x_{s}^{*},1)}
x
s
′
{\displaystyle x'_{s}}
U
(
t
)
{\displaystyle {\mathcal {U}}^{(t)}}
F
{\displaystyle F}
x
(
t
)
{\displaystyle x^{(t)}}
E
[
F
|
x
(
t
)
]
=
∑
s
∈
S
(
t
)
c
(
s
)
x
s
′
+
∑
s
∉
S
(
t
)
c
(
s
)
p
s
2
λ
c
⋅
x
∗
+
∑
e
∈
U
(
t
)
∏
s
∉
S
(
t
)
,
s
∋
e
(
1
−
p
s
)
.
{\displaystyle E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}
は反復後にのみ決定される ことに注意してください 。
E
[
F
|
x
(
t
)
]
{\displaystyle E[F|x^{(t)}]}
t
{\displaystyle t}
条件付き失敗確率を1未満に保つ 条件付き失敗確率を1未満に保つには、条件付き期待値を 1未満に保つだけで十分です。そのためには、条件付き期待値が 増加しないようにするだけで十分です。これがアルゴリズムが行うことです。 各反復で、
F
{\displaystyle F}
F
{\displaystyle F}
x
s
′
{\displaystyle x'_{s}}
E
[
F
|
x
(
m
)
]
≤
E
[
F
|
x
(
m
−
1
)
]
≤
⋯
≤
E
[
F
|
x
(
1
)
]
≤
E
[
F
|
x
(
0
)
]
<
1
{\displaystyle E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\leq E[F|x^{(0)}]<1}
（どこ ）。
m
=
|
S
|
{\displaystyle m=|{\mathcal {S}}|}
番目の反復で 、アルゴリズムは
を確実にするために をどのように設定するのでしょうか? 結果として得られる の値を 最小化する
ように を 単に設定すればよいことがわかります 。
t
{\displaystyle t}
x
s
′
′
{\displaystyle x'_{s'}}
E
[
F
|
x
(
t
)
]
≤
E
[
F
|
S
(
t
−
1
)
]
{\displaystyle E[F|x^{(t)}]\leq E[F|S^{(t-1)}]}
x
s
′
′
{\displaystyle x'_{s'}}
E
[
F
|
x
(
t
)
]
{\displaystyle E[F|x^{(t)}]}
理由を理解するには、反復が開始される時点に注目してください 。その時点では、 は決定されていますが、はまだ決定されていません 。
反復で が どのように設定されるかに応じて、2 つの値を取ることができます。 を の値とします 。 と を、 がそれぞれ 0 または 1 に設定されている かどうかに応じて、 の 2 つの値 とし ます。条件付き期待値の定義により、
t
{\displaystyle t}
E
[
F
|
x
(
t
−
1
)
]
{\displaystyle E[F|x^{(t-1)}]}
E
[
F
|
x
(
t
)
]
{\displaystyle E[F|x^{(t)}]}
x
s
′
′
{\displaystyle x'_{s'}}
t
{\displaystyle t}
E
(
t
−
1
)
{\displaystyle E^{(t-1)}}
E
[
F
|
x
′
(
t
−
1
)
]
{\displaystyle E[F|x'^{(t-1)}]}
E
0
(
t
)
{\displaystyle E_{0}^{(t)}}
E
1
(
t
)
{\displaystyle E_{1}^{(t)}}
E
[
F
|
x
(
t
)
]
{\displaystyle E[F|x^{(t)}]}
x
s
′
′
{\displaystyle x'_{s'}}
E
(
t
−
1
)
=
Pr
[
x
s
′
′
=
0
]
E
0
(
t
)
+
Pr
[
x
s
′
′
=
1
]
E
1
(
t
)
.
{\displaystyle E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}=1]E_{1}^{(t)}.}
2つの量の加重平均は常にその2つの量の最小値以上であるため、
E
(
t
−
1
)
≥
min
(
E
0
(
t
)
,
E
1
(
t
)
)
.
{\displaystyle E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).}
したがって、
の結果の値が最小になるように
を設定すると
、 になることが保証されます
。これがアルゴリズムが行うことです。
x
s
′
′
{\displaystyle x'_{s'}}
E
[
F
|
x
(
t
)
]
{\displaystyle E[F|x^{(t)}]}
E
[
F
|
x
(
t
)
]
≤
E
[
F
|
x
(
t
−
1
)
]
{\displaystyle E[F|x^{(t)}]\leq E[F|x^{(t-1)}]}
詳細に言うと、これは何を意味するのでしょうか。 の関数として考えると
（他のすべての量は固定）
、
は の線形関数であり 、 その関数における
の係数は
x
s
′
′
{\displaystyle x'_{s'}}
E
[
F
|
x
(
t
)
]
{\displaystyle E[F|x^{(t)}]}
x
s
′
′
{\displaystyle x'_{s'}}
x
s
′
′
{\displaystyle x'_{s'}}
c
s
′
2
λ
c
⋅
x
∗
−
∑
e
∈
s
′
∩
U
t
−
1
∏
s
∉
S
(
t
)
,
s
∋
e
(
1
−
p
s
)
.
{\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}
したがって、この式が正の場合、アルゴリズムは 0 に設定され、そうでない場合は 1 に設定する必要があります。これにより、次のアルゴリズムが得られます。
x
s
′
′
{\displaystyle x'_{s'}}
集合被覆のためのランダム丸めアルゴリズム 入力: セットシステム 、ユニバース 、コストベクトル
S
{\displaystyle {\mathcal {S}}}
U
{\displaystyle {\mathcal {U}}}
c
{\displaystyle c}
出力: 集合被覆 (集合被覆の標準整数線形計画法の解)
x
′
{\displaystyle x'}
最小コストの分数集合カバー （LP 緩和の最適解）を計算します。
x
∗
{\displaystyle x^{*}}
とします 。 各 についてとします 。
λ
←
ln
(
2
|
U
|
)
{\displaystyle \lambda \leftarrow \ln(2|{\mathcal {U}}|)}
p
s
←
min
(
λ
x
s
∗
,
1
)
{\displaystyle p_{s}\leftarrow \min(\lambda x_{s}^{*},1)}
s
∈
S
{\displaystyle s\in {\mathcal {S}}}
それぞれについて以下 を実行します。
s
′
∈
S
{\displaystyle s'\in {\mathcal {S}}}
とします 。( にはまだ決定されていない集合が含まれます。)
S
←
S
−
{
s
′
}
{\displaystyle {\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}}
S
{\displaystyle {\mathcal {S}}}
もし
c
s
′
2
λ
c
⋅
x
∗
>
∑
e
∈
s
′
∩
U
∏
s
∈
S
,
s
∋
e
(
1
−
p
s
)
{\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _{s\in {\mathcal {S}},s\ni e}(1-p_{s})}
次に設定し 、
x
s
′
←
0
{\displaystyle x'_{s}\leftarrow 0}
それ以外の場合は設定し て 。
x
s
′
←
1
{\displaystyle x'_{s}\leftarrow 1}
U
←
U
−
s
′
{\displaystyle {\mathcal {U}}\leftarrow {\mathcal {U}}-s'}
( まだカバーされていない要素が含まれています。)
U
{\displaystyle {\mathcal {U}}}
戻る 。
x
′
{\displaystyle x'}
補題（アルゴリズムの近似保証） 上記のアルゴリズムは、 任意の（分数）セットカバーの最小コスト の最大倍のコストのセットカバーを返します。
x
′
{\displaystyle x'}
2
ln
(
2
|
U
|
)
{\displaystyle 2\ln(2|{\mathcal {U}}|)}
証拠 アルゴリズムは 、、
の 条件付き期待値が各反復で増加しないことを保証します。この条件付き期待値は最初は 1 未満であるため (前述のとおり)、アルゴリズムは条件付き期待値が 1 未満に留まるようにします。失敗の条件付き確率は最大でも の条件付き期待値であるため 、このようにしてアルゴリズムは失敗の条件付き確率が 1 未満に留まるようにします。したがって、最後にすべての選択が決定されると、アルゴリズムは成功した結果に到達します。つまり、上記のアルゴリズムは、最大で 任意の (分数) セット カバーの最小コスト
の倍のコストのセット カバーを返します。
F
{\displaystyle F}
E
[
F
|
x
(
t
)
]
{\displaystyle E[F\,|\,x^{(t)}]}
F
{\displaystyle F}
x
′
{\displaystyle x'}
2
ln
(
2
|
U
|
)
{\displaystyle 2\ln(2|{\mathcal {U}}|)}
上記の例では、アルゴリズムはランダム変数の条件付き期待値によって導かれました 。場合によっては、正確な条件付き期待値の代わりに、何らかの条件付き期待値の 上限 （または下限）が使用されます。これは 悲観的推定量 と呼ばれます。
F
{\displaystyle F}
確率的手法の他の応用との比較 ランダム化された丸め手順は、 確率的方法 のほとんどのアプリケーションとは2 つの点で異なります。
丸めステップの計算の複雑さは重要です。これは高速な（例えば多項式時間）アルゴリズムによって実装可能で ある 必要 が あり ます 。 ランダム実験の基礎となる確率分布は、問題インスタンスの緩和 の 解の関数です 。この事実は、 近似アルゴリズムの パフォーマンス保証を証明するために重要です。つまり、どの問題インスタンスに対しても、アルゴリズムは その特定のインスタンスの最適解を 近似する解を返します。これと比較して、 組み合わせ論における確率的方法の応用は、 通常、入力の他のパラメータに依存する特徴を持つ構造の存在を示します。たとえば、 トゥランの定理 を考えてみましょう。これは、「 平均次数の頂点を 持つどの グラフも 、少なくとも のサイズの 独立集合 を持たなければならない」と述べることができます 。( トゥランの定理の確率的証明については、こちらを 参照してください。)この境界が厳密なグラフもありますが、 よりもはるかに大きい独立集合を持つグラフもあります 。したがって、トゥランの定理によってグラフ内に存在することが示される独立集合のサイズは、一般に、そのグラフの最大独立集合よりもはるかに小さい可能性があります。
x
{\displaystyle x}
n
{\displaystyle n}
d
{\displaystyle d}
n
/
(
d
+
1
)
{\displaystyle n/(d+1)}
n
/
(
d
+
1
)
{\displaystyle n/(d+1)}
参照
参考文献
さらに読む アルトファー、インゴ (1994)、「ランダム化戦略と凸結合に対するスパース近似について」、 線形代数とその応用 、 199 :339–355、 doi : 10.1016/0024-3795(94)90357-3 、 MR 1274423 ホフマイスター、トーマス; レフマン、ハンノ (1996)、「スパース近似の決定論的計算」、 線形代数とその応用 、 240 :9–19、 doi : 10.1016/0024-3795(94)00175-8 、 MR 1387283 リプトン、リチャード J.、ヤング、ニール E. (1994)、「大規模ゼロサムゲームのシンプルな戦略と複雑性理論への応用」、 STOC '94: 第 26 回 ACM コンピューティング 理論 シンポジウム議事録 、 ニューヨーク、NY: ACM 、 pp . 734–740、 arXiv : cs.cc/0205035、doi:10.1145/195058.195447、ISBN 978-0-89791-663-9 、 S2CID 7524887 
![{\displaystyle E[F]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab1eaeaaa0d398f7c1928e2e8f6034df5c5d7df2)
![{\displaystyle E[F]<1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/409c36e44d7e8d37388f8540f0c77b0eb8de60c6)
![{\displaystyle E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b4a0f26997d597abf26fbe964c068f6053067b3)
![{\displaystyle E[F|x^{(t)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c516a943b0bdd80258c376b5f8c1312053aaf424)
![{\displaystyle E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\leq E[F|x^{(0)}]<1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c6cb865ee3b08fa419708af3cfed1dc6a5ce517)
![{\displaystyle E[F|x^{(t)}]\leq E[F|S^{(t-1)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b535100a74df93c4420a34bd772b9a81a442294e)
![{\displaystyle E[F|x^{(t-1)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e19ee8fcae52cc8e549fb8e3892af7407475b9ad)
![{\displaystyle E[F|x'^{(t-1)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3aeb85012f79daa3ce7869dd3e917c6f7ea5b7d)
![{\displaystyle E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}=1]E_{1}^{(t)}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c40f3457ae5fee1ff53c6e152a1a785df3afce83)
![{\displaystyle E[F|x^{(t)}]\leq E[F|x^{(t-1)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45fcc2ef91a9e7ecf9a5dc53b4a36240c85ea004)
![{\displaystyle E[F\,|\,x^{(t)}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f02bf2b2f61e16478696d455a024e064e4ae675)
