劣モジュラ費用集合被覆問題
8
0
0
全文
(2) .
(3)
(4)
(5) ! "
(6) #
(7) $ " " %
(8)
(9) &' $ ( )
(10)
(11) *
(12) * + +
(13) ( % "
(14) " ,- " " " "
(15) . . ) "
(16) *
(17)
(18) / 0
(19) *
(20) & 1 . * *
(21)
(22) 1
(23) (. + *
(24) * * "
(25) % % * # "
(26)
(27)
(28) 2
(29)
(30)
(31) "
(32) 2 3
(33)
(34)
(35) + * 2 /
(36) 2 & #
(37) . 2 % . * "
(38)
(39) * 4 " 5
(40) 2 " & # 0
(41)
(42) . . 劣モジュラ費用集合被覆問題 岩. 田. 覚. Ý. 永 野 清 仁Ý. 本研究では，頂点被覆問題，枝被覆問題，集合被覆問題，それぞれの目的関数を線 形な関数から非負な劣モジュラ関数で置き換えて一般化した問題を扱う．これらの問 題に対し，劣モジュラ関数の離散凸性を用いた近似アルゴリズムを設計する．まず， 劣モジュラ頂点被覆問題に対しては，連続緩和問題の半整数性を証明し，それ利用し たラウンディングによる 近似アルゴリズムを与えた．さらに半整数的な最適解が劣 モジュラ関数最小化によって求まることを示した．劣モジュラ費用集合被覆問題に対 しては，最大重複度が定数でおさえられる場合，ラウンディングアルゴリズムと主双 対アルゴリズムの両方で定数近似率が達成されることを示した．劣モジュラ枝被覆問 題に対しては，近似可能性の本質的にタイトな下界を与えた．.
(43)
(44) Ý
(45) Ý
(46)
(47) .
(48)
(49)
(50)
(51)
(52) !. . "
(53)
(54)
(55) . #
(56) ! " $
(57) %
(58)
(59)
(60)
(61) . .
(62)
(63) %
(64) #
(65)
(66)
(67)
(68)
(69)
(70) #
(71)
(72) .
(73)
(74)
(75)
(76) #! "
(77)
(78)
(79)
(80)
(81)
(82)
(83) %
(84)
(85)
(86)
(87)
(88)
(89)
(90)
(91)
(92)
(93) % & # $ !. .
(94)
(95)
(96) # .
(97)
(98) #
(99) !. Ý 京都大学
(100) Ý 東京工業大学 . . . . ''(
(101) #
(102)
(103).
(104) Vol.2009-AL-126 No.3 2009/9/15. 情報処理学会研究報告
(105) . Æ * 5 + . Æ
(106) "
(107) * . *
(108) 5 " " > 1 4 "
(109) *
(110)
(111) * *
(112) "
(113) % * *
(114) " Æ
(115) 4
(116) 5 & (. + <? 1$
(117) / * ,- * Æ
(118)
(119) *
(120) > . = * . * % " * *
(121) (
(122) * & > % / * . "
(123) 0 " " " 0 % * ( 0 .
(124) ( 8 * Æ 0 " " ( @ * " +
(125) ( A *
(126) *
(127) / 2 3
(128)
(129)
(130) # 0 * 2 B % B % * 4
(131) * 2 B % * # 0 * 2 B *
(132) /
(133) ,
(134) * + * 2 .
(135) 2 * " "
(136)
(137) " & #
(138) " . . " 2 % . * ,- Æ 0 " . * & # 0
(139) .
(140) . " % * 2 2 2 * "
(141)
(142) " & #
(143) . 2 % . *
(144)
(145) 6
(146) 3789 & # 0
(147) .
(148) . % * 2 2 :
(149) *
(150) ;
(151)
(152) (*
(153) % *
(154) * ) . , " . $ " " , % : $ " " * " . " . " $ " " % " , % "
(155) " " 0 * *
(156) * " <" ; * . " . " / . " != < !
(157) " %
(158) .
(159) . Æ Æ Æ < . . . . . . ''(
(160) #
(161)
(162).
(163) Vol.2009-AL-126 No.3 2009/9/15. 情報処理学会研究報告
(164) . . * *
(165) - 2 * - +
(166) *
(167) 2 %
(168)
(169)
(170) Æ
(171)
(172)
(173) < &
(174) 2 +
(175) * 2 %
(176) *
(177)
(178)
(179) #2
(180) 3 %
(181) " - " 2 - + 2 3
(182)
(183)
(184) * 2 / *
(185) 2
(186) *
(187) 2 B % #
(188) . * $ " ,
(189) + # 0 * #
(190) *
(191) % 2
(192) *
(193) 2 3 2 B ; *
(194) " C
(195)
(196) ! 2 !
(197) ! B
(198) +
(199)
(200) * 2 " - 0 * "
(201) %
(202) 6B 39 * " * "
(203)
(204) ( D
(205) 6B 39 D
(206) *
(207) E "
(208) " %
(209) % * *
(210) "
(211) . $
(212)
(213) * " " $ " # 0 / " " 0 " + * *
(214) "
(215)
(216)
(217) / * " * . % . " * -1 C " " " 3 " B
(218) , % * -1 % * . "
(219) ! 6 . F39 # B 3
(220) . . . . . . . . . . . . #. %
(221) -1
(222) - 0 " " != < 0 " 4 / * " )-1 " # )-1 C " " " 3 " B
(223) %
(224)
(225) )-1 . . . .
(226)
(227)
(228) . . . . . . "Æ )-1 ) 2
(229)
(230)
(231) "Æ "Æ "Æ % "Æ * . ( - C " " " 3 " "
(232) B 2 3
(233)
(234)
(235) 3 " B
(236) . . . ). . ''(
(237) #
(238)
(239).
(240) Vol.2009-AL-126 No.3 2009/9/15. 情報処理学会研究報告
(241) . % 2 $
(242) * % #2 $ % % . "
(243) %
(244) . A )-1
(245) " .
(246) * " + * 2 % " 5
(247)
(248) 2 " , * 2 0
(249) " * * 0 "
(250) 8 + * 2 . *
(251) " 4 .
(252) "
(253) @3 - ; " " 5
(254) %
(255) @0 5 "
(256) % * "
(257) @8
(258) " != < # " %
(259) / * " + . % 2 & %
(260) ' .
(261)
(262) . , % Æ " ( - B 3 " * * * !
(263) . 0
(264) " " ; ( - " * )-1. ! "
(265) " )-1 % #2 " " % * * 0 " " #
(266) 0
(267) . % " "
(268) " 2 * #2 " 2 3 % " 2 ( " " )-1 * " 2
(269) " % * 0" 0 . . . . £. ¼. . . . / * " )1-
(270) /
(271)
(272)
(273)
(274)
(275) /
(276)
(277) ) 2
(278) G * " %
(279) 2
(280)
(281) + "
(282) * .
(283) 4
(284) "
(285)
(286)
(287)
(288) " $
(289)
(290) " 2 )-1. . +
(291) " )-1 * %
(292) " 2 " 2 3 2 " " " 2 6 9 )
(293)
(294) "
(295) " 2 )-1 " 2 6 9 6 9 % " )-1
(296) " 2 . . "
(297) . . .
(298) !
(299) * %
(300) . . . +
(301)
(302) % - F
(303)
(304) " #! "
(305) ) " . " #. + " $ H$ $
(306) H$ 2 $ +
(307) $ * $ 2
(308) "
(309) H$ / *
(310) % 2 $
(311)
(312) H$ %
(313) * ,
(314) "
(315)
(316) 2
(317) % 2 % % + . . ()- C " " 3 " B
(318) *. . ''(
(319) #
(320)
(321).
(322) Vol.2009-AL-126 No.3 2009/9/15. 情報処理学会研究報告
(323) . ; *
(324) " % ()- * . %
(325) * Æ # 0
(326) Æ 2 $ Æ $
(327) Æ )
(328) . * 6( 839 !
(329) Æ % "
(330) * " Æ" + Æ Æ Æ 5. $ $ $ 2 % 2 Æ
(331) " ()- % & 2 " 3 & Æ , & Æ
(332) " . % * * & Æ " ( .
(333) & Æ & Æ
(334) . . . E)- C" ( - ( 2 ( B
(335) % . ( E)- & % * ( #2 B #2 B & #2 ( * 2 B E)- * & 2 & / & *
(336) & % ( * E)- % & 5 " * & 2 & % & % *
(337) * &
(338)
(339) )
(340)
(341) )
(342) % * - ( #2 B #2 B & #2
(343) % 1 * 33 3@ & + , ( #2 + !, ) ! #2 ") ) - + , - ( #2 ( ! #2 ! + #, I & 5 " * & 2 &
(344) % ! 1 &
(345) . E)- & / *
(346) ( ) -
(347) ) ! ( 30 6 9 2 %
(348) ,* * % . 2 ! 3 , & 2 & & 2 B % 5 ( 38 2 & 2 & * & 2 &
(349)
(350) % & ( 3@ % . / *
(351) " % * * " . . . ( " " ()- * " 2
(352) % Æ
(353) % * " Æ " 2 Æ Æ Æ Æ Æ " 2 & 2 & % * & . . . Æ ". . . . ,
(354) Æ % Æ 4 * * " Æ * Æ
(355) # " %
(356) / * " ()- & "
(357) * " 2 "" - % " 5 * * ' C . . . ' ' 2 " . ' B
(358). . . % ()- * # C . . ' " 3 ' 2 " . ' B
(359). . +. . ''(
(360) #
(361)
(362).
(363) Vol.2009-AL-126 No.3 2009/9/15. 情報処理学会研究報告
(364) . -
(365) . . !
(366) . . . & .
(367)
(368) 2
(369) .
(370) . . . . !
(371)
(372) * ( ( (
(373) ( & * & 2 & *
(374) ( E)- & 2 & 2 ( (
(375) 4
(376) * 2 ( (
(377) % * &
(378) . . . . . . . . . +. . . % .
(379) . 2 . . +. +. . % % 3B * * 2 * 0 %
(380) + / . * + Æ 2 4-% 2 J 4-% 2 4 *
(381) 8@ * 4-% 2 3 0 % " * " % 2 * 2 %
(382) 2 3 * + *
(383) *
(384) , 6B 39 * , * * / * 2 + E - 2 6 + 9 2 3, % , * + *
(385) <? 1$
(386) * 6% . K3@9 ! <? 1$
(387) # , 8 0 &
(388)
(389) +' 2 +
(390)
(391) 3
(392) + * . * ! % * *. * ) : / + 0 0 , .
(393)
(394)
(395) . .
(396) -. 2 3 2 , -. 2 B 2 3 , . 2 - 2 6. 9 2 , ( ! L- -. ! " ! , * * , 2 % 30 " - 2 + . ( - 2 6 + 9 2 3 * . 38 - + L- " L- 2 " @ 3 2
(397) 8. ! % %
(398)
(399) * * * * ,- .
(400) " * * * " "
(401) 4
(402) * . & (. + %
(403) @3 " / *
(404) * % * * * B #
(405) . 4
(406)
(407)
(408) 2 $
(409)
(410)
(411)
(412) % .
(413) " * % % 3B * * % * . "
(414) 6 . 039
(415) 0 . . . . ,. . ''(
(416) #
(417)
(418).
(419) Vol.2009-AL-126 No.3 2009/9/15. 情報処理学会研究報告
(420) . ( 7-, 2 * @ - . 38 - & + 8F 2 - & + L - & + L- " L- " 80
(421) ;
(422) * 7- * - + 8F - & + 8F 2
(423) A !
(424) @ A * - 2 . - 2 & + 2 , 7-. %
(425) 1 )
(426) ) * * 0 # 2 - 2 - + 8F +
(427) %
(428) + 1 + 4-% 2 2 3 0 / * * 4-% 4-% *
(429) % 3B # # 2 +
(430)
(431) 4-% 2 J 4-% 2 4 . I . 33 3A * * . ' (
(432) . +
(433) * 0 ( - 2 3 * 4-% - 0 2 J ) * 2 + ( + * 4-% 2 - 8F 0 2 4 . .
(434) &
(435)
(436) 2. . .
(437) . +'
(438) . . &
(439) %%
(440) +
(441) * % 3B. ,
(442) + Æ
(443) % * % 3B
(444) "
(445) + 2 5 $ ( +
(446)
(447)
(448) , 2 &.
(449)
(450) +' 2 . . 2
(451)
(452) / " * / 2 * *
(453) % * * *
(454) 8@ / Æ
(455)
(456)
(457) /
(458) * * *
(459) 3 3 3 2 * . 3@ 4-% 2 J / 4-% 2 4 / 2 * 2 *
(460) 30 * )
(461) 3F. 7- % * * 7-
(462) / Æ
(463) ( 7- % + L- - + + - + 2 2 - % * 8 * - 2 - + L- 2
(464) ( 7- !
(465) 2 + 8F % - 2 - + 8F
(466) @ )
(467) 5
(468) @ " * * 2 7- &
(469) & 2 7- . . " #$! % . C $ ;$ " ( . %& 3 1 != ( <# " * "
(470) ! 37L3 37LM0B8 0 !! $ #
(471) - 37LA -. . ''(
(472) #
(473)
(474).
(475) Vol.2009-AL-126 No.3 2009/9/15. 情報処理学会研究報告
(476) . NF3MNNN 37 ( * O ! 4#
(477) ,(
(478)
(479) 0BB7 308BM308N 0B ( > 4 1 # K" " * 0 * (# 0BBL 88AM8@7 03 )> . ,= # &
(480) Q " *
(481) # ( ) 0BB7 - ,)( AAAA F8@MFA0 00 O K C . K , C (. # C" . .
(482) $
(483) "
(484) 0BB7 808M880 08 $ # ( "
(485)
(486) "
(487)
(488) ! C&' !> ( K 37L8 08AM0AN 0@ C C < I # !! . * .
(489) !! ) I
(490) - 0BBA 0A > , # C<%1 0BBN@8 I
(491) % .
(492) O
(493) 0BBN 0F & , < % O# - " .
(494)
(495)
(496) ' 37N@ @LMF3 0N = , # (
(497) * 0BBA 30NM3A0 0L = , # <" 5 " ) ' 0BBA 08AM0@7 07 O ! 4#
(498)
(499) .
(500) - 0BB7 08NM0A3 8B ( # .
(501)
(502) ! "
(503) ! -* 0BBB 8@FM8AA 83 ( # ! ) * -
(504) %Æ ( K 0BB8 80 R (. + # ( " # *
(505) $/
(506) %%% & 0BBL F7NMNBF 88 K K K # 0
(507) ( K 0BB3 8@ O K $.# 4 " *
(508) $(
(509) "
(510) 0BBL FNMN@. 8 + ) . > , # <Æ " * $ " "
(511)
(512)
(513) 0BBN N7MLL @ O < # (
(514) ! "
(515) 1 &
(516) ; ; , ( O( ' & ! 37NB F7MLN A -<? 1$
(517) # 4 "
(518) # ( 37FF 8A7M8FL F I + K C . O K $.# C"
(519) $
(520) %%% & 0BBN @F3M@N3 N + ( *# * .
(521) 0BB8 833M800 L (+ # % (
(522) ) < 0BBA 7 && )> -% / # "
(523) *
(524) '(
(525) %%% & 0BB7 3B CP& , ;
(526) 1 > K C .# 4 C 0BBL 33 C P & K ( 1 . # C ! $ 377A @77MA38 30 C &' $ ( # % 5 ! 37L3 3F7M37N 38 C &' $ ( #
(527) ! ) * ( K ! 37LL 3@ ;
(528)
(529) ) (*
(530) <$ % # ,* . * .
(531) +
(532) .
(533) 0BBA 788M7@0 3A E(; # " " 37L0 AAAMAAF 3F E ( ; , C O , % # % 0 " * * 5
(534)
(535) '! 3778 F7ML8 3N ( *# ! 0BB8 L88ML@B 3L ( * + ( + #
(536)
(537)
(538) #- 0BB3 .. . ''(
(539) #
(540)
(541).
(542)
関連したドキュメント
節点領域辺連結度 (node-to-area edge-connectivity), 領域間辺連結度 (area-to-area edge-connectivity) の問題. ･優モジュラ関数
FOCS2007: Maximizing non-monotone submodular functions, by Uriel Feige, Vahab Mirrokni and Jan Vondrak..
Murota: Discrete Convex Analysis (SIAM Monographs on Dis- crete Mathematics and Applications 10, SIAM, 2003). Fujishige: Submodular Functions and Optimization (Annals of
（約13万店）は、一般廃棄物に ついて収集運搬業の許可不要 で、収集運搬費用徴収可能（処 分費用は預り金）.
携帯電話の SMS（ショートメッセージサービス：電話番号を用い
収入の部 学会誌売り上げ 前年度繰り越し 学会予算から繰り入れ 利息 その他 収入合計 支出の部 印刷費 事務局通信費 編集事務局運営費 販売事務局運営費
収入の部 学会誌売り上げ 前年度繰り越し 学会予算から繰り入れ 利息 その他 収入合計 支出の部 印刷費 事務局通信費 編集事務局運営費 販売事務局運営費
（参考）系統連系希望者がすべて旧費用負担ルール ※４ 適用者 ※５ の場合における工事費用 特定負担 約１,３１０百万円.. ※１
