I Submodular välfärd Maximization (SWM) problem, indata består av en uppsättning av n objekt, som var och en måste tilldelas en av m agenter. Varje agent har en värdering funktion v, där v (S) betecknar den välfärd som erhålls av denna agent om hon får uppsättningen av objekt S. Funktionerna v är alla submodulära; som är standard, antar vi att de är monoton och v (∅) = 0. Målet är att dela upp objekten i m separata undergrupper S1, S2,. .. Sm för att maximera den sociala välfärden, definieras som m = 1 v (S ). En enkel girig algoritm ger en 1/2-uppskattning till SWM i offline-inställningen, och detta var den mest kända tills Vondrak nyligen (1 − 1/e)-uppskattning algoritm [34]. I detta dokument överväger vi online-versionen av SWM. Här, objekt anländer en åt gången på ett online sätt; när ett objekt anländer, algoritmen måste göra ett oåterkalleligt beslut om vilken agent att tilldela det innan du ser några efterföljande objekt. Detta problem motiveras av applikationer för Internetreklam, där användare annons intryck måste tilldelas annonsörer vars värde är en submodulär funktion av den uppsättning användare / intryck de får. Det finns två naturliga modeller som skiljer sig åt i den ordning i vilken föremål anländer. I den helt kontradiktoriska inställningen, kan en motståndare konstruera en godtycklig / värsta fall instans, samt välja den ordning i vilken objekt anländer för att minimera algoritmens prestanda. I denna inställning är den 1/2-konkurrenskraftiga giriga algoritmen den bästa möjliga. För att förbättra på detta måste man försvaga motståndaren något: I slumpmässig ordning modell, motståndaren kan konstruera en värsta fall uppsättning poster och värderingar, men inte kontrollera den ordning i vilken objekten anländer; istället antas de komma i en slumpmässig ordning. Den slumpmässiga ordermodellen har studerats väl för SWM online och olika specialfall, men det mest kända konkurrensförhållandet (även för flera specialfall) är 1/2 + 1/n [9, 10], knappt bättre än förhållandet för den kontradiktoriska ordern. Det har under flera år varit ett viktigt öppet problem att få fram ett konkurrensförhållande på 1/2 + 1 för den slumpmässiga ordermodellen. Vi löser detta öppna problem genom tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar, och att kopior bär detta meddelande och den fullständiga hänvisning på första sidan. Upphovsrätt till tredje parts delar av detta arbete måste hedras. För all annan användning, kontakta ägaren/författarna. Upphovsrätten innehas av upphovsmannen/ägarna. visar att den giriga algoritmen har ett konkurrensförhållande på minst 0.505 för online SWM i slumpmässig ordning modell. Detta är det första resultatet som visar en konkurrenskvot som är begränsad till mer än 1/2 i den slumpmässiga ordermodellen, även i specialfall som de viktade matchnings- eller budgeterade tilldelningsproblemen (utan de så kallade "stora kapacitets antagandena"). För specialfall av submodulära funktioner, inklusive viktade matchningsfunktioner, viktade täckningsfunktioner och en bredare klass av "andra klassens supermodulära" funktioner, tillhandahåller vi en annan analys som ger ett konkurrensförhållande på 0,51. Vi analyserar den giriga algoritmen med hjälp av ett faktoruppenbarande linjärt program, som begränsar hur tilldelningen av ett objekt kan minska potentiella välfärd från att tilldela framtida objekt. Vi formulerar också ett naturligt antagande som, om det är sant, skulle förbättra konkurrensförhållandet mellan den giriga algoritmen till minst 0,567. Utöver våra nya konkurrensförhållanden för SWM online gör vi ytterligare två bidrag: För det första definierar vi de klasser av modulära, supermodulära och submodulära funktioner som sannolikt kommer att vara av oberoende intresse för submodulära optimeringar. För det andra får vi ett förbättrat konkurrensförhållande via en teknik som vi hänvisar till som vinst linjärisering, vilket kan vara användbart i andra sammanhang (se [26] ): I huvudsak, vi linjärisera submodulär funktion genom att dividera vinsten av en optimal lösning i vinst från enskilda element, jämföra algoritmens vinst när det tilldelar ett element till den optimala lösningens vinst från elementet, och, avgörande nog, avgränsa i vilken utsträckning tilldela element kan påverka den potentiella vinsten av andra element.
Korula m.fl. REF visar att girig får en 0,505-approximation i slumpmässig ordning modell.
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}