複数制約式をもつ0-1ナップサック多面体の体積に対するFPTAS
4
0
0
全文
(2) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-AL-152 No.6 2015/3/3. を 計算する 問題に 対し て FPTAS を 示す． のア イ ディ ア に ついて 説明し ， 体積を 畳み込み積分の繰り. こ の場合は命題が正し いこ と がわかる ． 次に， 帰納法の仮定と し て Pr A[j−1] X[j−1] ≤ x が成立. 返し で表す方法に つ いて 説明する ． 第３ 節では Km (b) の. る こ と を 示す．. 本稿は次のよ う に 構成さ れて いる ． 第２ 節では提案手法. 体積に 対する FPTAS を 示す． そ の後， 第４ 節でま と めと 今後の課題を 述べる ．. 2. 一様分布に 従う 確率変数の列と Km (b) の 体積について X = (X1 , . . . , Xn ) を [0,h1]n に 一様に 分布し た i 確率変 V ⊤ 数と す る ． す る と ， 事象 i=1,...,m ai X ≤ bi と 事 象 [X ∈ Km (b)] が 同値で あ る こ と は 明ら か で あ る ． す な わち ，. . Pr . ^. i=1,...,m. . =. であ る ． f (x)， F (x) を そ れぞれ [0, 1] 上の一様分布の密度 関数と 分布関数と する ．. f (x) =. . 0. 0 ≤ x ≤ 1, otherwise,. Pr A[j] X[j] ≤ x Z +∞ = Pr A[j] X[j] ≤ x | Xj = s f (s)ds −∞ X1 . Z +∞ . . Pr A[j] = ≤ x f (s)ds −∞ Xj−1 s # Z +∞ " ^ m [a1 X1 + · · · + ai−1 Xi−1 + ai s ≤ xi ] f (s)ds = Pr −∞. a⊤ i X ≤ bi. Vol(Km (b)) = Vol(Km (b)) = Pr [X ∈ Km (b)] = Vol([0, 1]n ). 1. する と 仮定する ． こ の時， j に ついて 同様の指揮が成立す. 0 x ≤ 0, F (x) = x 0 ≤ x ≤ 1, 1 x ≥ 1.. こ こ で， Ψ0 : Rm → R を 帰納的に 定義する ． 1 when x ≥ 0, Ψ0 (x) = 0 otherwise.. Z. +∞. Pr −∞. i=1. "m ^. #. [a1 X1 + · · · + ai−1 Xi−1 ≤ xi − ai s] f (s)ds. i=1. X1 +∞ . . = Pr A[j−1] . ≤ x − sAj f (s)ds −∞ Xj−1 Z +∞ = Ψi−1 (x − sAj )f (s)ds Z. . . −∞. = Ψi (x). 以上よ り ， 命題が正し いこ と が示さ れた ．. ✷. 3. 提案手法について 提案手法は Ψj (x) を j = 1, . . . , n のそれぞれの場合につ いて m 次元の階段近似を 行う こ と であ る ． こ の際， 近似 を 行う 範囲は x = (x1 , . . . , xm ) と し て ， 0 ≤ xi ≤ jbi (i =. 次に， j = 1, 2, . . . , n について 漸化式を 用いて Ψj : Rm → R を 定義する ．. m 1, . . . , m) であ る ． ま ず x ∈ R≥0 の場合 G0 (x) = 1， そ う. でな い場合は G0 (x) = 0 と する ． 次に， 記述を 容易にする. Ψj (x) =. Z. ∞. Ψj−1 (x − sAj )f (s)ds,. −∞. た だ し x = (x1 , . . . , xm ) ∈ Rm で あ る ． ま た ， A の 1 列 目から j 列目を 取り 出し た 部分行列 A[j] = (A1 . . . Aj ) お よ び ， X の 1, . . . , j 番目の要素を 取り 出し た 部分ベク ト ル X [j] = (X1 , . . . , Xj ) を 定義する . する と 次のこ と が言 える ． 命題 1 j ∈ {1, 2, . . . , n} と x ∈ Rm に ついて ，. Ψj (x) = Pr A[j] X[j] ≤ x. −∞. = Pr A[1] X[1] ≤ x. ⓒ 2015 Information Processing Society of Japan. A1 s≤x. (2). −∞. そ し て ， Gj (x) は Gj (x) を m 次元の階段近似し た も のと する ． つま り ， Gj (x) = Gj (z), where z ⊤ = (z1 , . . . , zk )， であ り ， i = 1, . . . , m に ついて M xi jbi zi = max 0, min jbi , jbi M であ る ． こ こ ではすべて の値を 記憶する た め， 一つの j に. 証明 帰納法で証明を 行う ． ま ず j = 1 の場合に ついて 考え る ． 定義よ り ， Z +∞ Z Ψ1 (x) = Ψ0 (x − A1 s)f (s)ds =. た めの中間的な シン ボルと し て Gj (x) を 考え る ． Z ∞ Gj (x) = Gj−1 (x − sAj )f (s)ds,. ついて ， Gj (x) を 格納する のに O(M m ) のス ペース を 用い る ． 最後に ， Gn (b) を 出力し て 提案手法は終了する ． 以下が提案手法の擬似コ ード であ る ．. f (s)ds. Algorithm1 m 入力: a1 , . . . , am ∈ Zn >0 , b ∈ Z>0 .. 1. G0 (x) := 0 for x 6∈ Rm ≥0 , 2.
(3) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-AL-152 No.6 2015/3/3. G0 (x) := 1 for x ∈ Rm ≥0 と する ;. 繰り 返すた め， 次の補題を 得る ． 補題 1. 2. For j = 1, . . . , n 3.. For each x ∈ {0, ..., M }. 提案手法は O(mM m+1 n(τ m + log(mM ))) 時間. で完了する ．. m. 4.. i = 1, . . . , m に ついて zi := xi bi /M と する ;. 5.. Gj (z) を 計算する ． た だし z = (z1 , . . . , zm ); ⊤. 6. Gn (b) を 出力する ．. 残り は M を ど れだ け 大き く と る こ と で 近似比. Gn (b)/Ψn (b) を 1 + ǫ 以 内 に で き る か と い う 部 分 で あ Pj hbi る ． ま ず， L⊤ j = (ℓ1j , . . . , ℓmj ) た だ し ℓij = h=1 M = j(j+1) bi 2M. 3.1 実行時間解析. (i = 1, . . . , m) と する ． する と 次の補題が証明で. きる． 2. こ こ では， Gj (x) が O(τ m M + mM log mM ) 時間で計 算でき る こ と を 示す． た だし ， τ は四則演算に かかる 時間 であ る ． f (x) は一様分布の確率密度関数な ので， Z 1 Gj (x) = Gj−1 (x − sAj )ds. 補題 2. 上述のよ う に Ψj (x), Gj (x) and Gj (x) が定義. さ れる と き ， j = 0, . . . , n に ついて. Ψj (x) ≤ Gj (x) ≤ Ψj (x + jLj ) (3). 0. であ る ．. であ る ． こ の積分式 (3) は有理数の和と し て 計算でき る ．. 以下は m 変数関数の平均値の定理と し て 知ら れて いる ．. 式 (3) の計算のた めに は， 階段近似の格子を な す超平面と. 定理 1. ℓ ∈ Rm と し ， F (x) (x = (x1 , . . . , xm ) ∈ Rm ). 積分路の交点 O(mM ) 個を 計算する ． 得ら れた交点を ソ ー. は x1 , . . . , xm のそれぞれよ っ て 微分可能である と する ． す. ト し た のち ， 式 (3) を O(τ m2 M ) 時間で計算する ．. る と ， 実数 0 ≤ θ ≤ 1 が存在し て. 階段近似の格子を なす超平面は， j 番目の次元について 式. F (x + ℓ) = F (x) + ℓ⊤ f (x + θℓ). xj = hjbi /M (h ∈ Z) で与え ら れる ． Gj (x) の計算に あ た っ て は， ま ず x − sAj (0 ≤ s ≤ 1) で与え ら れる 積分路 と 格子を な す超平面の交点を 計算する ． ま ず j = 1, . . . , n に つ いて ， j 番目の次元の格子線と 積分路の交点を 計算 する ． 得ら れる 交点を t1 , . . . , tu ∈ Rm と する ． こ れら の 交点は一次方程式 xi − saij = hjbi /M を s に つ い て 解 く こ と で 得ら れる (h = 1, . . . , M ,. i = 1, . . . , m)． そ し. て t1 , . . . , tu のう ち 一つを 求める た めに は， 得ら れた s を 使っ て 他の m − 1 個の成分を 求める ． よ っ て ， t1 , . . . , tu は O(τ u) = O(τ m2 M ) 時間で計算でき る ． 次に t1 , . . . , tu を ソ ー ト する ． こ の時のソ ー ト 順は ai′ を Aj の非 0 成分と し た と き の， i′ 番目の成分の昇順であ る ． ク イ ッ ク ソ ート 等を 用いる と 計算時間は O(u log u) で あ る ． 以後， t1 , . . . , tu は昇順に ソ ート 済みであ る と する ． 以上の計算のあ と ， Gj (x) を. Gj (x) =. u X. |tk+1 − tk |Gj−1 (tk+1 ),. が成立する ． た だし ，. f ⊤ (x) = ∇f (x) =. . ∂F ∂F (x), . . . , (x) ∂x1 ∂xm. . であ る ． あ る 一つの x ∈ Rm が与え ら れた 場合， 以下の補題が成 立する ． 補題 3. 任意の ǫ > 0 について M ≥ mn2 (n + 1)/(2ǫ) と. する と 入力と し て 与え ら れた b に対し て Ψn (b) ≤ Gn (b) ≤. (1 + ǫ)Ψn (b + Ln ) であ る ． 以上の内容から た だち に 定理 2 が示せる ． 定理 2. 任意の ǫ > 0 に つ いて Km ((b)) を 近似比 1 + ǫ. で計算する 決定性近似ア ルゴ リ ズム が存在し ， 実行時間は. O(mm+3 n3m+4 (2ǫ)−m−1 (τ m + log(mnǫ−1 ))) で あ る ． た だし ， τ は四則演算に かかる 時間であ る ．. (4). k=0. 4. ま と めと 今後の課題. と し て 計算で き る ． た だ し ， t0 = x, tu+1 = x − Aj で. #P -困 難 な 問 題 に 対 す る FPTAS 設 計 の 技 法 に 刺 激. あ り ， |t| はユ ー ク リ ッ ド ノ ル ム で あ る ． 一つ x が 与え. を 受け て ， 本論文で は 制約式を m 個持つ 0 − 1 ナ ッ プ. ら れ た と し て ， Gj (x) を 計算す る た め に 提案手法で は. サ ッ ク 多面体の 体積を 計算す る 問題を 考え ， そ の FP-. |tk+1 − tk |Gj−1 (tk − Aj ) を O(τ m) 時間で計算し ， u 回繰. TAS を 示し た ． 提案手法は 畳み 込み 積分を 階段近似す. り 返す．. る こ と を 繰り 返す 手法で あ る ． 提案手法の 実行時間は. 提案手法では Gj (x) の計算を (M + 1)m 回繰り 返す． 一. O(mm+3 n3m+4 (2ǫ)−m−1 (τ m + log(mnǫ−1 ))) で あ り ， m. つの Gj (x) の値を 計算する のに かかる 時間が O(τ m2 M +. が定数であ れば実行時間は n と 1/ǫ の多項式であ る ． 実行. mM log(mM )) である ので， Gj の値すべて を Gj−1 から 計. 時間に は削減の余地が多く 残さ れて いて ， ア ルゴ リ ズム に. 算する のに かかる 時間は O(mM k+1 (τ m + log(mM ))) で. 工夫を 加え る こ と でよ り 高速な も のを 作る こ と ができ る 見. あ る ． 提案手法を よ り 工夫する こ と で実行時間は更に短縮. 込みである ． ま た， 提案手法を 他の #P -困難な 問題に適用. する こ と が可能であ る が， 簡単のた めこ こ ではそ の内容に. する こ と は今後の課題であ る ．. ついて は触れな い． Gj (x) の計算は j = 1, . . . , n に ついて ⓒ 2015 Information Processing Society of Japan. 3.
(4) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-AL-152 No.6 2015/3/3. 謝辞 本研究は文部科学省 科学研究費補助金 新学術領 域研究「 多面的ア プロ ーチ の統合に よ る 計算限界の解明」. [20]. (No. 24106008, 24106005) の助成を 受け た も のです． 参考文献. [21]. [1]. [22]. [2]. [3] [4]. [5] [6]. [7]. [8]. [9]. [10]. [11]. [12] [13]. [14]. [15]. [16] [17]. [18]. [19]. E. Ando and S. Kijima, An FPTAS for The Volume Computation of 0-1 Knapsack Polytopes Based on Approximate Convolution Integral, Proc. of ISAAC 2014, pp.376–386, 2014. A. Bandyopadhyay and D. Gamarnik, Counting without sampling: asymptotics of the log-partition function for certain statistical physics models, Random Structures and Algorithms, 33, 452–479, 2008. I. B´ar´any, Z. F¨ uredi, computing the volume is difficult, Discrete Computational Geometry, 2, 319–326, 1987. M. Bayati, D. Gamarnik, D. Katz, C. Nair, P. Tetali, Simple deterministic approximation algorithms for counting matchings, Proc. of STOC 2007, 122–127, 2007. M. Dyer, Approximate counting by dynamic programming, Proc. of STOC 2003, 693–699, 2003. M. Dyer and A. Frieze, On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, 17(5), 967–974, 1988. M. Dyer, A. Frieze, R. Kannan, A random polynomialtime algorithm for approximating the volume of convex bodies, Journal of the Association for Computing Machinery, 38(1), 1–17, 1991. G. Elekes, A geometric inequality and the complexity of computing volume, Discrete Computational Geometry, 1, 289–292, 1986. D. Gamarnik, D. Katz, Correlation decay and deterministic FPTAS for counting list-colorings of a graph, Proc. of SODA 2007, 1245–1254, 2007. P. Gopalan, A. Klivans, and R. Meka, Polynomialtime approximation schemes for knapsack and related counting problems using branching programs, arXiv:1008.3187v1, 2010. ˇ P. Gopalan, A. Klivans, R. Meka, D. Stefankoviˇ c, S. Vempala, E. Vigoda, An FPTAS for #knapsack and related counting problems, Proc. of FOCS 2011, 817– 826, 2011. Ker-I Ko, Complexity Theory of Real Functions, Birkh¨auser, Boston, 1991. L. Li, P. Lu, Y. Yin, Approximate counting via correlation decay in spin systems, Proc. of SODA 2012, 922–940, 2012. L. Li, P. Lu, Y. Yin, Correlation decay up to uniqueness in spin systems, Proc. of SODA 2013, 67–84, 2013. J. Li, T. Shi, A fully polynomial-time approximation scheme for approximating a sum of random variables, Operations Research Letters, 42, 197–202, 2014. C. Lin, J. Liu, P. Lu, A simple FPTAS for counting edge covers, Proc. of SODA 2014, 341–348, 2014. L. Lov´asz, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM Society for industrial and applied mathematics, Philadelphia, 1986. L. Lov´asz, S. Vempala, Simulated annealing in convex bodies and an O ∗ (n4 ) volume algorithm, Journal of Computer and System Sciences, 72, 392–417, 2006. S. Mitra, On the probability distribution of the sum of uniformly distributed random variables, SIAM Jour-. ⓒ 2015 Information Processing Society of Japan. nal on Applied Mathematics, 20(2), 195–198, 1971. ˇ D. Stefankoviˇ c, S. Vempala, E. Vigoda, A deterministic polynomial-time approximation scheme for counting knapsack solutions, SIAM Journal on Computing, 41(2), 356–366, 2012. K. Weihrauch, Computable Analysis An Introduction, Springer-Verlag, Berlin, 2000. D. Weitz, Counting independent sets up to the tree threshold, Proc. STOC 2006, 140–149, 2006.. 4.
(5)
関連したドキュメント
Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework.. SIAM Journal on Optimization,
Hungarian Method Kuhn (1955) based on works of K ő nig and
Yin, “Markowitz’s mean-variance portfolio selection with regime switching: a continuous-time model,” SIAM Journal on Control and Optimization, vol... Li,
In addition to the basic facts just stated on existence and uniqueness of solutions for our problems, the analysis of the approximation scheme, based on a minimization of the
For the time step Δt 0.05 seconds, the decays of the total potential energy and the angular momentum, shown in Figures 11a and 11b, respectively, are practically the same for
Toshihiro Shirakawa and Ryuhei Uehara Common Developments of Three Different Orthogonal Boxes, The 24th Canadian Conference on Computational Geometry CCCG 2012, pp... The bible of
FPSO
凡例及び面積 全体敷地 2,800㎡面積 土地の形質の変更をしよ うとする場所 1,050㎡面積 うち掘削を行う場所
