@inproceedings{81d5b9ea5a5344b48383f49a0916995c,
title = "Beyond Pointwise Submodularity: Non-monotone Adaptive Submodular Maximization Subject to Knapsack and k-System Constraints",
abstract = "Although the knapsack-constrained and k-system-constrained non-monotone adaptive submodular maximization have been well studied in the literature, it has only been settled given the additional assumption of pointwise submodularity. In this paper, we remove the common assumption on pointwise submodularity and propose the first approximation solutions for both knapsack and k-system constrained adaptive submodular maximization problems. Inspired by two recent studies on non-monotone adaptive submodular maximization, we develop a sampling-based randomized algorithm that achieves a 110 approximation for the case of a knapsack constraint and that achieves a 12k+4 approximation ratio for the case of a k-system constraint.",
keywords = "Adaptive submodularity, Approximation algorithms, Non-monotonicity",
author = "Shaojie Tang",
note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 4th International conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, MCO 2021 ; Conference date: 11-12-2021 Through 13-12-2021",
year = "2022",
doi = "10.1007/978-3-030-92666-3\_2",
language = "English",
isbn = "9783030926656",
series = "Lecture Notes in Networks and Systems",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "16--27",
editor = "\{Le Thi\}, \{Hoai An\} and Le, \{Hoai Minh\} and \{Le Thi\}, \{Hoai An\} and \{Pham Dinh\}, Tao",
booktitle = "Modelling, Computation and Optimization in Information Systems and Management Sciences - Proceedings of the 4th International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences - MCO 2021",
address = "Germany",
}