Vi studerar adaptive influence maximization problem med myopic feedback under den oberoende kaskadmodellen: en sekventiellt väljer k noder som frön en efter en från ett socialt nätverk, och varje valt frö returnerar de omedelbara grannarna det aktiverar som feedback tillgänglig för senare val, och målet är att maximera det förväntade antalet totala aktiverade noder, kallas påverkan spridning. Vi visar att anpassningsgapet, förhållandet mellan den optimala adaptiva påverkansspridningen och den optimala icke adaptiva påverkansspridningen, är högst 4 och minst e/(e‐1), och approximationsförhållandet med avseende på den optimala adaptiva påverkansspridningen av både icke adaptiva giriga och adaptiva giriga algoritmer är minst (e+1) 2 < 1 − 1 e. Dessutom är approximationsförhållandet för den icke adaptiva giriga algoritmen inte sämre än för den adaptiva giriga algoritmen, när man beaktar alla grafer. Vårt resultat bekräftar ett långvarigt öppet antagande av Golovin och Krause (2011) om den konstanta approximationen av adaptiv girig med myopisk feedback, och det tyder också på att adaptiv girig kanske inte ger någon större nytta under myopisk feedback.
Peng och Chen REF visade att anpassningsgapet för den oberoende kaskadmodellen med myopisk återkoppling är som högst 4 och minst e/e − 1), och de visade också att både adaptiva och icke adaptiva giriga algoritmer utför en 0,25 (1 – 1/e) - approximation till den adaptiva optimala lösningen.
2 8 M ay 2 01 9 Adaptive Influence Maximization with Myopic Feedback