Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions

DOI10.1137/1.9781611974331.CH31MaRDI QIDQ4575608zbMATH OpenOpenAlexFDO

Authors Ashwinkumar Badanidiyuru, Aviad Rubinstein, Lior Seeman, Y. Singer, Christos Papadimitriou

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.02351

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Stochastic programming (90C15) Approximation algorithms (68W25)

Abstract: The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes in a network, and then select, adaptively, among neighbors of those nodes as they become accessible in order to maximize a global objective function. More generally, adaptive seeding is a stochastic optimization framework where the choices in the first stage affect the realizations in the second stage, over which we aim to optimize. Our main result is a $(1-1/e{)}^2$-approximation for the adaptive seeding problem for any monotone submodular function. While adaptive policies are often approximated via non-adaptive policies, our algorithm is based on a novel method we call emph{locally-adaptive} policies. These policies combine a non-adaptive global structure, with local adaptive optimizations. This method enables the $(1-1/e{)}^2$-approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies. We also introduce a fundamental problem in submodular optimization that may be of independent interest: given a ground set of elements where every element appears with some small probability, find a set of expected size at most $k$ that has the highest expected value over the realization of the elements. We show a surprising result: there are classes of monotone submodular functions (including coverage) that can be approximated almost optimally as the probability vanishes. For general monotone submodular functions we show via a reduction from extsc{Planted-Clique} that approximations for this problem are not likely to be obtainable. This optimization problem is an important tool for adaptive seeding via non-adaptive policies, and its hardness motivates the introduction of emph{locally-adaptive} policies we use in the main result.

Recommendations

• Partial-monotone adaptive submodular maximization
• Robust and Adaptive Sequential Submodular Optimization
• Adaptive robust submodular optimization and beyond
• Partial-adaptive submodular maximization
• Monotone submodular maximization over a matroid via non-oblivious local search
• scientific article; zbMATH DE number 3846704
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Robust Adaptive Submodular Maximization

Cited in

(6)

• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Better bounds on the adaptivity gap of influence maximization under full-adoption feedback
• Greedy algorithm for maximization of semi-monotone non-submodular functions with applications
• Generalized budgeted submodular set function maximization
• Generalized budgeted submodular set function maximization
• Fixed observation time-step: adaptive influence maximization

This page was built for publication: Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575608)