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

DOI10.1016/J.TCS.2020.11.007zbMATH Open1467.68218arXiv2008.05004OpenAlexW3048806178MaRDI QIDQ2216441FDOQ2216441

Authors: Shaojie Tang 

Publication date: 16 December 2020

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

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.

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

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

zbMATH Keywords

cardinality constraintsubmodular maximizationadaptive submodularity

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• Title not available (Why is that?)
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Price of dependence: stochastic submodular maximization with dependent items
• Influence maximization with partial feedback

Cited In (17)

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

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)