Adapting Seeding är en viktig algoritmisk utmaning för påverkansmaximering i sociala nätverk. Man försöker välja bland vissa tillgängliga noder i ett nätverk, och sedan, adaptivt, bland grannar till dessa noder när de blir tillgängliga, för att maximera inflytandet i det totala nätverket. Trots den senaste tidens starka approximation resultat [Seeman och Singer 2013; Badanidiyuru et al. 2015], mycket lite är känt om problemet när noder kan ta på olika aktiveringskostnader. Förvånansvärt, utforma adaptiv såningsalgoritmer som på lämpligt sätt kan motivera användare med heterogena aktiveringskostnader inför grundläggande utmaningar som inte finns i den förenklade versionen av problemet. I detta dokument studerar vi ungefärligheten av adaptiva såningsalgoritmer som uppmuntrar noder med heterogena aktiveringskostnader. Vi visar först ett snävt, omisskännligt resultat som gäller även för en mycket begränsad version av problemet. Vi kompletterar sedan denna otillnärmelse med en konstant faktor approximation för allmänna submodulära funktioner, vilket visar att de svårigheter som orsakas av den stokastiska karaktären av problemet kan övervinnas. Dessutom visar vi starkare approximativa resultat för additiv påverkan och fall där nodernas aktiveringskostnader utgör en liten del av budgeten.
Rubinstein, Seeman och Singer REF presenterar adaptiva algoritmer för val av noder med heterogena kostnader.
Approximability of Adaptive Seeding under Knapsack Constraints
{'venue': "EC '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}