Maximizando uma função submodular de dois conjuntos com diferentes restrições de tamanho

Eu tenho dois domínios totalmente distintos (maçãs e laranjas) e eu tenho uma função que pega um conjunto de objetos do primeiro domínio e um conjunto de objetos do segundo domínio e retorna um número real.$f$

possui as seguintes propriedades interessantes:$f(S,T)$

• fixando , é não negativo, submodular e monótono wrt S ;$T$$S$

• fixação , que é não-negativo, submodulares e monótona wrt T .$S$$T$

Eu quero maximizar com duas restrições de cardinalidade | S | = S e | T | = t .$f(S,T)$$|S| = s$$|T| = t$

Como eu posso fazer isso? Se considerar o espaço do produto, a função é monótona e submodular. Assim, posso aplicar o algoritmo ganancioso padrão. Lidar com as duas restrições de tamanho diferentes pode não ser um problema: adicionar e ( a , y ) em sequência permite aumentar | T | sem aumentar | S | .$(a, x)$$(a, y)$$|T|$$|S|$

A questão é se a aproximação ainda é válida.$1-1/e$

$(V,E)$$V=V_1 \uplus V_2$$f(S,T)$$S \subseteq V_1, T \subseteq V_2$$S$$T$$f$$f(S,\cdot)$$f(\cdot,T)$$a=b=k$$k$$k$