Maximizar una función submodular de dos conjuntos con diferentes restricciones de tamaño

Tengo dos dominios totalmente distintos (manzanas y naranjas) y tengo una función que toma un conjunto de objetos del primer dominio y un conjunto de objetos del segundo dominio y devuelve un número real.$f$

tiene las siguientes propiedades interesantes:$f(S,T)$

• fijando , es no negativo, submodular y monótono wrt S ;$T$$S$

• la fijación de , es no negativo, submodular y monótona wrt T .$S$$T$

Quiero maximizar con dos restricciones de cardinalidad | S | = S y | T | = t .$f(S,T)$$|S| = s$$|T| = t$

¿Cómo puedo hacer eso? Si considero el espacio del producto, la función es monótona y submodular. Por lo tanto, puedo aplicar el algoritmo codicioso estándar. Tratar con las dos restricciones de tamaño diferentes puede no ser un problema: agregar y ( a , y ) en secuencia me permite aumentar | T | sin aumentar | S | .$(a, x)$$(a, y)$$|T|$$|S|$

La pregunta es si la aproximación aún se mantiene.$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$