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

8

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 ;TS

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

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.11/e

Francesco Bonchi
quelle
4
f(,)=f({s},)=f(,{t})=0f({s},{t})=1
2
Danke, guter Punkt. Vergessen wir also den zweiten Teil meiner Frage. Irgendeine Idee, wie man eine solche Funktion maximiert?
Francesco Bonchi

Antworten:

10

(V,E)V=V1V2f(S,T)SV1,TV2STff(S,)f(,T)a=b=kkk

Chandra Chekuri
quelle