Adaptive Seeding problem är en algoritmisk utmaning som motiveras av inflytande maximering i sociala nätverk: Man försöker välja bland vissa tillgängliga noder i ett nätverk, och sedan välja, adaptivt, bland grannar till dessa noder som de blir tillgängliga för att maximera en global objektiv funktion. Mer allmänt, adaptiv sådd är en stokastisk optimering ram där valen i det första steget påverkar förverkligandet i det andra steget, över vilken vi syftar till att optimera. Vårt huvudsakliga resultat är en (1 - 1/ e) 2 - approximation för adaptiv sådd problem för någon monoton submodulär funktion. Adaptive policys approximas ofta via icke-adaptiva policys, men vår algoritm bygger på en ny metod som vi kallar lokalt adaptive policys. Dessa policyer kombinerar en icke-adaptiv global struktur, med lokala adaptiva optimeringar. Denna metod möjliggör (1 − 1/e) 2 - approximation för allmänna monotona submodulära funktioner och kringgår några av de omöjligheter som är förknippade med icke-adaptiva policyer. Vi introducerar också ett grundläggande problem i submodulära optimering som kan vara av oberoende intresse: med tanke på en mark uppsättning element där varje element visas med någon liten sannolikhet, hitta en uppsättning förväntad storlek som mest k som har det högsta förväntade värdet över förverkligandet av elementen. Vi visar ett överraskande resultat: det finns klasser av monotona submodulära funktioner (inklusive täckning) som kan paras nästan optimalt när sannolikheten försvinner. För allmänna monotona submodulära funktioner visar vi via en minskning från Planted-Clique att approximationer för detta problem sannolikt inte är möjliga att få. Detta optimeringsproblem är ett viktigt verktyg för adaptiv sådd via icke-adaptiva policies, och dess hårdhet motiverar införandet av lokalt adaptiva policies som vi använder i huvudresultatet. Vi använder följande bundet i tidningen (se till exempel [30, Theorem 4.4]). Teorin A.1. (Chernoff bunden) Antag X 1,. ., X n är oberoende slumpmässiga variabler tar värden i [0, 1] och låt X betecknar deras summa och μ vara det förväntade värdet av X. Därefter, för 0 < δ < 1 har vi att P r[X > (1 + δ)μ] ≤ exp(− δ 2 μ 3 ) 429
En approximationsalgoritm med förhållandet 1 – 1 e 2 har föreslagits i REF.
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
{'venue': 'Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms', 'journal': 'Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms', 'mag_field_of_study': ['Computer Science']}