Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time

DOI10.1016/J.TCS.2020.11.007MaRDI QIDQ2216441zbMATH OpenOpenAlexFDO

Authors Shaojie Tang

Publication date 16 December 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

adaptive submodularitycardinality constraintsubmodular maximization

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: In this paper, we study the non-monotone adaptive submodular maximization problem subject to a cardinality constraint. We first revisit the adaptive random greedy algorithm proposed in citep{gotovos2015non}, where they show that this algorithm achieves a $1/e$ approximation ratio if the objective function is adaptive submodular and pointwise submodular. It is not clear whether the same guarantee holds under adaptive submodularity (without resorting to pointwise submodularity) or not. Our first contribution is to show that the adaptive random greedy algorithm achieves a $1/e$ approximation ratio under adaptive submodularity. One limitation of the adaptive random greedy algorithm is that it requires $O(nimesk)$ value oracle queries, where $n$ is the size of the ground set and $k$ is the cardinality constraint. Our second contribution is to develop the first linear-time algorithm for the non-monotone adaptive submodular maximization problem. Our algorithm achieves a $1/e-epsilon$ approximation ratio (this bound is improved to $1-1/e-epsilon$ for monotone case), using only $O(nepsilo{n}^{-2}logepsilo{n}^{-1})$ value oracle queries. Notably, $O(nepsilo{n}^{-2}logepsilo{n}^{-1})$ is independent of the cardinality constraint. For the monotone case, we propose a faster algorithm that achieves a $1-1/e-epsilon$ approximation ratio in expectation with $O(nlogfrac1epsilon)$ value oracle queries. We also generalize our study by considering a partition matroid constraint, and develop a linear-time algorithm for monotone and fully adaptive submodular functions.

Recommendations

• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• Partial-monotone adaptive submodular maximization
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint

Cites work

• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Influence maximization with partial feedback
• Price of dependence: stochastic submodular maximization with dependent items

Cited in

(20)

• Adaptive robust submodular optimization and beyond
• Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
• Partial-monotone adaptive submodular maximization
• Streaming adaptive submodular maximization
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
• Robust Adaptive Submodular Maximization
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Streaming adaptive submodular maximization
• Constrained stochastic submodular maximization with state-dependent costs
• Partial-adaptive submodular maximization
• Data summarization beyond monotonicity: non-monotone two-stage submodular maximization
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
• Online non-monotone diminishing return submodular maximization in the bandit setting
• Achieving long-term fairness in submodular maximization through randomization
• A fast algorithm for submodular maximization with a matroid constraint
• Adaptive combinatorial maximization: beyond approximate greedy policies

This page was built for publication: Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time

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