コンピュータサイエンス、特に 近似アルゴリズム の研究 において 、
L-縮約 （「 線形縮約」）は、近似可能性の特徴を線形に保存する 最適化問題 の変換であり、 近似保存縮約 の一種です。 最適化問題 の近似可能性の研究におけるL-縮約は、 意思決定問題 の 計算複雑性 の研究における 多項式縮約 と同様の役割を果たします 。
L 削減という 用語は、 複雑性クラス Lとの類推により、 対数空間削減 を指すために使用されることがあります が、これは異なる概念です。
意味 AとBを 最適化問題 とし、c A とc Bをそれぞれのコスト関数とします。関数 f と g のペアは、 以下の条件をすべて満たす場合、L縮約となります。
関数 f と gは 多項式時間 で計算可能であり 、 xが 問題Aの例であれ ば、 f ( x )は問題Bの例である。 y'が f ( x ) の解 ならば g ( y' )は x の解であり 、 正の定数αが存在し、
O
P
T
B
(
f
(
x
)
)
≤
α
O
P
T
A
(
x
)
{\displaystyle \mathrm {OPT_{B}} (f(x))\leq \alpha \mathrm {OPT_{A}} (x)}
、 正の定数βが存在し、 f ( x ) のあらゆる解 y'に対して
|
O
P
T
A
(
x
)
−
c
A
(
g
(
y
′
)
)
|
≤
β
|
O
P
T
B
(
f
(
x
)
)
−
c
B
(
y
′
)
|
{\displaystyle |\mathrm {OPT_{A}} (x)-c_{A}(g(y'))|\leq \beta |\mathrm {OPT_{B}} (f(x))-c_{B}(y')|}
。
プロパティ
PTAS削減の影響 問題Aから問題BへのL-還元は、 AとBが最小化問題である場合は AP-還元を、AとBが最大化問題である場合は PTAS-還元を 意味します。どちらの場合も、BにPTASがあり、AからBへのL-還元がある場合、AにもPTASがあります。 [1] [2] これにより、PTAS-還元の存在を示す代わりにL-還元を使用することができます。Crescenziは、より自然なL-還元の定式化は、使いやすさから、多くの場合、実際にはより有用であると示唆しています。 [3]
証明（最小化の場合） Bの近似比を とする 。まずAの近似比から始める 。AとBは最小化問題であることが分かっているので、L-縮約定義の3番目の条件の周りの絶対値は取り除くことができる。この条件を代入して、
1
+
δ
{\displaystyle 1+\delta }
c
A
(
y
)
O
P
T
A
(
x
)
{\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}
c
A
(
y
)
O
P
T
A
(
x
)
≤
O
P
T
A
(
x
)
+
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
)
O
P
T
A
(
x
)
{\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq {\frac {\mathrm {OPT} _{A}(x)+\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}}
単純化して最初の条件を代入すると、
c
A
(
y
)
O
P
T
A
(
x
)
≤
1
+
α
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
O
P
T
B
(
x
′
)
)
{\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq 1+\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)}
しかし、右辺の括弧内の項は実際には に等しい 。したがって、Aの近似比は である 。
δ
{\displaystyle \delta }
1
+
α
β
δ
{\displaystyle 1+\alpha \beta \delta }
これは AP 削減の条件を満たしています。
証明（最大化の場合） Bの近似比を とする 。まずAの近似比から始める 。AとBは最大化問題であることが分かっているので、L-縮約定義の3番目の条件の周りの絶対値は取り除くことができる。この条件を代入して、
1
1
−
δ
′
{\displaystyle {\frac {1}{1-\delta '}}}
c
A
(
y
)
O
P
T
A
(
x
)
{\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}
c
A
(
y
)
O
P
T
A
(
x
)
≥
O
P
T
A
(
x
)
−
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
)
O
P
T
A
(
x
)
{\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq {\frac {\mathrm {OPT} _{A}(x)-\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}}
単純化して最初の条件を代入すると、
c
A
(
y
)
O
P
T
A
(
x
)
≥
1
−
α
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
O
P
T
B
(
x
′
)
)
{\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq 1-\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)}
しかし、右辺の括弧内の項は実際には に等しい 。したがって、Aの近似比は である 。
δ
′
{\displaystyle \delta '}
1
1
−
α
β
δ
′
{\displaystyle {\frac {1}{1-\alpha \beta \delta '}}}
の場合 、 となり 、PTAS 削減の要件は満たしますが、AP 削減の要件は満たしません。
1
1
−
α
β
δ
′
=
1
+
ϵ
{\displaystyle {\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon }
1
1
−
δ
′
=
1
+
ϵ
α
β
(
1
+
ϵ
)
−
ϵ
{\displaystyle {\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}}
その他の特性 L-還元は P-還元 も意味します。 [3] この事実とP-還元がPTAS還元を意味するという事実から、L-還元はPTAS還元を意味すると推論できます。
L 削減は、AP 削減を意味する結果として、最小化する場合にのみ APX のメンバーシップを保持します。
例
参照
参考文献
^ Kann, Viggo (1992). NP完全\mathrm{OPT}imization問題の近似可能性について . スウェーデン王立工科大学. ISBN 978-91-7170-082-7 。 ^ Christos H. Papadimitriou; Mihalis Yannakakis (1988). 「\mathrm{OPT}imization, approximation, and Complexity Classes」. STOC '88: Proceedings of the twentieth annual ACM Symposium on Theory of Computing . doi : 10.1145/62212.62233 . ^ ab Crescenzi, Pierluigi (1997). 「近似値保存型縮約の簡易ガイド」. Proceedings of Computational Complexity. 第12回IEEEカンファレンス . ワシントンD.C.: IEEE Computer Society. pp. 262–. doi :10.1109/CCC.1997.612321. ISBN 9780818679070 . S2CID 18911241。
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. 複雑性と近似. 組合せ最適化問題とその近似可能性. 1999年, Springer. ISBN 3-540-65431-3 
