INTERSECTION OVER UNION IS NOT A SUBMODULAR FUNCTION

[yiskw713]

INFO

author

KERDONCUFF Tanguy, EMONET Rémi

affiliation

Univ Lyon, UJM-Saint-Etienne, CNRS, Institut d Optique Graduate School,

conference or year

2018

link

pdf

概要

IOUは劣モジュラ関数ではないことの証明を行った記事． 劣モジュラ関数の説明はこちらがわかりやすい．

IOUはを直接最小化するためには，IOUと同値で微分可能な関数を探す必要があり，既存研究ではその一つの方法として，Lovasz approzimation(#84 ) が行われてきた．列モジュラ関数の Lovasz Extention は凸関数となるが，実際にはIOUは劣モジュラ関数ではなく，その Lovasz Extention は凸とはならない．

証明もかなり簡単．#84 は誤りであることが示された．

用語

• 台集合mの冪集合2^m (台集合のすべての部分集合から作り出される集合) 例) 台集合 A = {1, 2} の冪集合は {∅, {1}, {2}, {1, 2}}

date

Oct 4th, 2019