Reforços da submodularidade

13

Uma função de ajuste é submodular monótono se para todos , A , B f ( A ) + f ( B ) f ( A B ) + f ( A B ) .fUMA,B

f(A)+f(B)f(UMAB)+f(UMAB).

Uma propriedade mais forte é Tomando C = A \ cup B , essa propriedade implica submodularidade monótona.C=AB

f(UMA)+f(B)+f(C)+f(UMABC)f(UMAB)+f(BC)+f(UMAC)+f(UMABC).
C=UMAB

Esta propriedade é conhecida?

fundo

Essa propriedade surgiu ao tentar caracterizar as funções de cobertura. Dado alguns universo ponderada você (todos os pesos são para não-negativa) e uma família X de subconjuntos de você , a função de cobertura f(S) é definida por SX como o peso total de elementos cobertos por conjuntos em S . A função f é sempre monótona e submodular. O contrário não é verdade.

A propriedade em questão implica que f é uma função de cobertura no caso |X|=3 . Propriedades semelhantes e mais complicadas funcionam para um X maior X. Todas essas propriedades são satisfeitas pelas funções de cobertura, portanto, essa é uma caracterização completa.

Yuval Filmus
fonte

Respostas:

13

Existe uma caracterização completa das funções de cobertura em termos de tais equações. Para | X |> 3, existem mais equações do que as apontadas. Cada uma dessas equações pode ser pensada como uma restrição na derivada discreta .kth

Função de aumento monotônico se e somente se a derivada discreta de primeira ordem for + ve. isto é, quando .f(B)-f(UMA)0 0UMAB

Submodularidade se e somente se a derivada discreta de segunda ordem for -ve. ou seja, .(f(UMAB)-f(B))-(f(UMA)-f(UMAB))0 0

Da mesma forma, se você tiver condições nos próximos derivados, obterá funções de cobertura. (Acho que os sinais precisam ser + ve para derivada de ordem par e -ve para derivada de ordem ímpar)n

Algo semelhante já era conhecido em probabilidade. Uma função de cobertura também pode ser pensada como uma medida de probabilidade (até uma constante de escala). A única referência que consegui desenterrar foi a página 439 do livro de Feller sobre probabilidade.

Ashwinkumar BV
fonte
Obrigado pela referência! A condição da derivada discreta é um pouco diferente, pois você considera adicionar apenas um elemento por vez. A monotonicidade é sim e a submodularidade é . Este último é de fato equivalente à condição usual somente quando nenhum de é um subconjunto do outro. Portanto, minha propriedade de terceira ordem (que requer as anteriores em geral) não aparece no artigo. f(UMA{x})f(UMA)f(UMA{x})+f(UMA{y})f(UMA{x,y})+f(UMA)UMA,B
Yuval Filmus
7

f(UMAB)+f(UMAC)+f(BC)+f((UMAB)(UMAC)(BC))f(UMA(BC))+f(B(UMAC))+f(C(UMAB))+f(UMABC).
A condição "agregada" é mencionada no artigo "Uma caracterização de um cone de funções pseudo-booleanas através de desigualdades do tipo supermodularidade" por Cramma, Hammer e Holtzman (desigualdade (4)), que faz parte da rara coleção "Métodos quantitativos in den Wirtschaftswissenschaften ". Essa condição deve ser a mesma que a minha.

f(UMA)+f(B)+f(C)+f(UMABC)f(UMABC)+f(UMAB)+f(UMAC)+f(BC).
C=
Yuval Filmus
fonte