I detta dokument studerar vi anpassningsgapet i påverkansmaximeringsproblem enligt oberoende kaskadmodell när full adoptionsfeedback finns tillgänglig. Våra huvudsakliga resultat är att härleda övre gränser på flera familjer av välstuderade påverkan grafer, inklusive in-arborescences, out-arborescences och bipartite grafer. Särskilt, vi bevisar att anpassningsgapet för in-arborescence är mellan [ e-1, 2e e-1 ] och för ut-arborescence, gapet är mellan [ e-1, 2]. Dessa är de första konstanta övre gränserna i full-adoption feedback-modellen. Vi tillhandahåller flera nya idéer att hantera med korrelerad feedback som visas i adaptiv stokastisk optimering, som vi anser vara av oberoende intressen.
Anpassningsgapet för den oberoende kaskadmodellen med återkoppling med full adoption, liksom anpassningsgapet för den linjära tröskelmodellen med båda återkopplingsmodellerna, är fortfarande öppna problem, även om det finns vissa partiella framsteg REF.
On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}