Med tanke på en uppsättning objekt och en samling av spelare, var och en med en icke-negativ monoton värdering uppsättning funktion över objekten, välfärdsmaximering problem kräver att varje objekt tilldelas exakt en spelare, och man vill maximera summan av värden som erhållits av spelarna, som beräknas genom att tillämpa respektive värdering funktion på bunten av objekt som tilldelats spelaren. Detta problem i sin fulla allmängiltighet är N P-hård, och dessutom minst lika svårt att approxima som set-packning. Bättre approximativa garantier är kända för begränsade kategorier av värderingsfunktioner. I detta arbete introducerar vi en ny parameter, den supermodulära graden av en värderingsfunktion, vilket är ett mått på i vilken utsträckning funktionen uppvisar supermodulärt beteende. Vi utformar en approximationsalgoritm för välfärdsmaximering problem vars approximation garanti är linjär i den supermodulära graden av de underliggande värderingsfunktioner.
Feige och Izsak REF införde en hierarki av monotone set funktioner, parameteriserade av den så kallade supermodulär grad.
Welfare maximization and the supermodular degree
{'venue': "ITCS '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}