劣加法的集合函数のソースを表示

[[数学]]における'''劣加法的集合函数'''（れつかほうてきしゅうごうかんすう、{{lang-en-short|''subadditive set function''}}）は、二つの集合の合併に対する値が、それぞれの集合に対する値の和で上から抑えられるような[[集合函数]]を言う。点函数が[[劣加法的函数|劣加法的]]となることに似ている。

: [[劣モジュラ函数|劣モジュラー]] ⊂ {{ill2|分割劣加法的|en|Fractionally subadditive set function}} ⊂ '''劣加法的'''

== 定義 ==
[[集合]] {{math|Ω}} 上の集合函数、すなわち {{math|Ω}} の[[冪集合]] {{math|2{{sup|Ω}}}} を定義域とする写像 {{math|''f'': 2{{sup|Ω}} → ''B''}} が'''劣加法的'''とは
: <math>f(S\cup T) \le f(S) + f(T)\quad (\forall S,T\subset \Omega)</math>
を満たすときに言う。[[終域]] {{mvar|B}} は任意の[[順序集合]]にもとれるが、大抵は[[実数直線]] {{mathbf|R}} または非負実数直線 {{math|'''R'''{{sub|+}}}} である{{sfn|Feige|2009}}{{page needed|date=2017年7月}}{{sfn|Dobzinski|Nisan|Schapira|2010}}{{page needed|date=2017年7月}}。

== 例 ==
* 任意の非負[[劣モジュラー集合函数]]は劣加法的集合函数である。劣モジュラー函数全体の成す集合は劣加法的函数全体の成す集合を真に含まれる。
* 与えられた集合 {{mvar|S}} を[[被覆 (集合論)|被覆]]するのに必要な集合の数を数える函数 {{math|''f''(''S'')}} は劣加法的である。具体的には、{{math|''T''{{sub|1}}, …, ''T{{sub|m}}'' ⊂ Ω}} で <math display="inline">\bigcup_{i=1}^m T_i=\Omega</math> となるものを固定する。{{mvar|f}} は各集合に対して、それを被覆するのに必要な {{mvar|T{{sub|i}}}} の最小数を割り当てるもの、すなわち <math display="block">
  f(S) := \min\Bigl\{t \mid \exists i_1,\dotsc,i_t \text{ s.t. } S\subset \bigcup_{j=1}^t T_{i_j}\Bigr\}
</math> とすれば、これは劣加法的になる。
* 任意の非負値[[加法的集合函数]]、特に[[測度]]は劣加法的である{{efn|一般に {{mvar|f}} が加法的集合函数ならば、{{math|1=''f''(''S'') + ''f''(''T'') = ''f''(''S'' ∪ ''T'') + ''f''(''T'' ∩ ''S'')}} と書けることに注意せよ。}}。
* より一般に、加法的函数{{efn|加法的集合函数 {{math|''{{tilde|a}}'': 2{{sup|Ω}} → '''R'''{{sub|+}}}} は {{math|''a''(''x'') {{coloneqq}} ''{{tilde|a}}''({{mset|''x''}})}} と置いて得られる点函数 {{math|''a'': Ω → '''R'''{{sub|+}}}} によって {{math|''{{tilde|a}}''(''S'') {{coloneqq}} {{sum|''x''∈''S''}} ''a''(''x'')}} と書くことができる}}のあつまり {{math|1=''{{tilde|a}}''{{sub|i}}: 2{{sup|Ω}} → '''R'''{{sub|+}} (''i'' = 1, …, ''m'')}} から[[点ごと|引数ごと]]に[[最大値|最大のもの]]をとる函数 {{math|''f''(''S'') {{coloneqq}} max{{sub|1=''i''=1,…,''m''}} ''{{tilde|a}}{{sub|i}}''(''S'') (∀S ⊂ Ω)}} は劣加法的になる{{efn|双対的に、加法的函数の集まりの[[最小値|最小]]をとれば[[優加法的]]である}}。
** このような函数は、以下の性質によって特徴付けられる{{sfn|Feige|2009}}{{page needed|date=2017年7月}}:
**; {{ill2|label=分割的劣加法性|分割的劣加法集合函数|en|Fractionally subadditive}}: 各 {{math|''S'' ⊂ Ω}} に対し、{{math|''X''{{sub|1}}, …, ''X{{sub|n}}'' ⊂ Ω}} および {{math|''α''{{sub|1}}, …, ''α{{sub|n}}'' ∈ {{closed-closed|0, 1}}}} が指示函数に関して {{math|'''1'''{{sub|''S''}} &le; {{sum|''i''{{=}}1|''n''}} ''α{{sub|i}}''&sdot;'''1'''{{sub|''X{{sub|i}}''}}}} を満たすならば必ず、{{math|1=''f''(''S'') &le; {{sum|''i''{{=}}1|''n''}} ''α{{sub|i}}''&sdot;''f''(''X{{sub|i}}'')}} を満たす。
** 分割的劣加法集合函数は劣モジュラー集合函数の一般化であり、かつ特別な種類の劣加法的集合函数である。

== 注 ==
=== 注釈 ===
{{notelist}}
=== 出典 ===
{{reflist}}

== 参考文献 ==
* {{cite article | first=Uriel | last=Feige | authorlink=Uriel Feige | title=On Maximizing Welfare when Utility Functions are Subadditive | journal=SIAM Journal on Computing | volume=39 | issue=1 | year=2009 | pages=122–142 | doi=10.1137/070680977|ref=harv}}
* {{cite article | first1=Shahar | last1=Dobzinski | first2=Noam | last2=Nisan | first3=Michael | last3=Schapira | authorlink2=Noam Nisan | title=Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders | journal=Mathematics of Operations Research | volume=35 | issue=1 | year=2010 | pages=1–13 | doi=10.1145/1060590.1060681|ref=harv}}

== 外部リンク ==
* {{SpringerEOM|urlname=Subadditive_function|title=Subadditive function}}

{{DEFAULTSORT:れつかほうてきしゆうこうかんすう}}
[[Category:組合せ最適化]]
[[Category:集合函数]]
[[Category:写像]]
[[Category:加法性]]
[[Category:数学に関する記事]]