Dada uma função submodular em que e são disjuntos . Aqui e são submodulares em e respectivamente.
Aqui são desconhecidos e apenas um acesso de consulta de valor a é fornecido. Então existe um algoritmo polytime que encontra . Se houver várias opções para qualquer uma delas deve estar correta.
Alguns pensamentos. Se pudermos encontrar dois elementos modo que ambos pertençam a ou pertençam a , podemos mesclá-los e prosseguir recursivamente. Mas não está claro como implementar essa etapa.
ds.algorithms
submodularity
Ashwinkumar BV
fonte
fonte
Respostas:
Tome um elemento arbitrário . Se , não é afetado pelo restante dos elementos, para que possamos escolher e . Caso contrário, seja um subconjunto mínimo de inclusivo para inclusão, de modo que . Então deve estar na mesma partição. Se , concluímos que não há partição desejada, caso contrário, reduzimos esse conjunto em um único elemento e recursamos.f ( e ) = f Ω - e ( e ) e X 1 = { e } X 2 = Ω - { e } X Ω - e f ( e ) > f X ( e ) X ∪ { e } X ∪ { e } = Ωe∈Ω f(e)=fΩ−e(e) e X1={e} X2=Ω−{e} X Ω−e f(e)>fX(e) X∪{e} X∪{e}=Ω
fonte