Regularized Unconstrained Weakly Submodular Maximization
Open Access
- 21 October 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 3537-3548
Abstract
Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form h = f-c, where f is a monotone, non-negative, weakly submodular set function and c is a modular function. We design a deterministic approximation algorithm that runs with O(n/ε log n/(γ ε) ) oracle calls to function h, and outputs a set S such that h(S) ≥ γ(1-ε)f(OPT)-c(OPT)-c(OPT)/γ(1-ε) log f(OPT)/c(OPT), where γ is the submodularity ratio of f. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of f. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function f, and Bayesian A-Optimal design for weakly submodular f. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Submodularity of optimal sensor placement for traffic networksTransportation Research Part B: Methodological, 2023
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid2019
- Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity2019
- Towards Profit Maximization for Online Social Network Providers2018
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular MaximizationSIAM Journal on Computing, 2015
- Maximizing Social Influence in Nearly Optimal Time2013
- Fast algorithms for maximizing submodular functions2013
- Maximizing a Monotone Submodular Function Subject to a Matroid ConstraintSIAM Journal on Computing, 2011
- A Human Protein-Protein Interaction Network: A Resource for Annotating the ProteomeCell, 2005
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978