Decompondo uma função submodular

9

Dada uma função submodular em que e são disjuntos . Aqui e são submodulares em e respectivamente.fΩ=X1X2X1X2f(S)=f1(SX1)+f2(SX2)f1f2X1X2

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.X1,X2,f1,f2fX1X1

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.t1,t2X1X2

Ashwinkumar BV
fonte
2
Você quer dizer que onde e são submodulares em e respectivamente? f(S)=f1(SX1)+f2(SX2)f1f2X1X2
Chandra Chekuri
Sim, eu realmente quis dizer isso. Obrigado por apontar o erro de digitação, eu o corrigirei.
Ashwinkumar BV 15/11
3
Não tenho certeza se o que digo abaixo está correto, mas aqui está a idéia. 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 . Parece que deve estar na mesma partição e, portanto, podemos reduzir o conjunto em um único elemento e recursar se for estritamente menor que ; caso contrário, concluímos que não existe uma partição desejada. eΩf(e)=fΩe(e)eX1={e}X2=Ω{e}XΩef(e)>fX(e)X{e}Ω
Chandra Chekuri
2
Decidiu transformar o comentário em uma resposta.
Chandra Chekuri

Respostas:

5

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)eX1={e}X2=Ω{e}XΩef(e)>fX(e)X{e}X{e}=Ω

Chandra Chekuri
fonte