Maximierung einer submodularen Funktion von zwei Sätzen mit unterschiedlichen Größenbeschränkungen

Ich habe zwei völlig unterschiedliche Domänen (Äpfel und Orangen) und ich habe eine Funktion , die eine Reihe von Objekten aus der ersten Domäne und eine Reihe von Objekten aus der zweiten Domäne nimmt und eine reelle Zahl zurückgibt.$f$

hat folgende interessante Eigenschaften:$f(S,T)$

• Fixierung von , es ist nicht negativ, submodular und monoton für S ;$T$$S$

• Befestigungs , ist es nicht negativ ist , und monotone submodularen WRT T .$S$$T$

Ich möchte maximieren mit zwei Mächtigkeit Einschränkungen | S | = s und | T | = t .$f(S,T)$$|S| = s$$|T| = t$

Wie kann ich das machen? Wenn ich den Produktraum betrachte, ist die Funktion monoton und submodular. Somit kann ich den Standard-Greedy-Algorithmus anwenden. Der Umgang mit den beiden unterschiedlichen Größenbeschränkungen ist möglicherweise kein Problem: Wenn Sie und ( a , y ) nacheinander hinzufügen , kann ich | erhöhen T | ohne zu erhöhen | S | .$(a, x)$$(a, y)$$|T|$$|S|$

Die Frage ist, ob die Näherung noch gilt.$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$