Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Abstract
Over the past decade, a growing body of research has shown that γ-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a γ-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative (1+1/γ)−2 factor established by \citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to ργ=1−(γ/(2−γ)) γ2/(2(1−γ)) . In sharp contrast to the previous guarantee, our obtained factor ργ not only strictly improves upon (1+1/γ)−2 for every γ∈(0,1], but also can asymptotically approach the optimal (1−1/e)-approximation for submodular maximization as γ→1. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of α-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of 1−e−γ and 1−e−α, respectively. Here, α∈(0,1] denotes the DR ratio.
Related
- Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms
- From Trees to Binary Trees: Approximation Algorithms and a PTAS
- Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
- Approximation Algorithms for Maximum-Weight Degree-Bounded Forests
- Theoretical Foundations and Effective Algorithms for Policy-Aware Simulator Learning
BibTeX
@misc{fu2026poisson,
title = {{Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids}},
author = {Shi Fu and Youming Qiao and Dacheng Tao and Zongqi Wan and Qixin Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24569},
eprint = {2609.24569},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24569},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
AU - Shi Fu
AU - Youming Qiao
AU - Dacheng Tao
AU - Zongqi Wan
AU - Qixin Zhang
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.24569
UR - https://arxiv.org/abs/2609.24569
AB - Over the past decade, a growing body of research has shown that γ-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a γ-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative (1+1/γ)^−2 factor established by \citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to ρ_γ=1−(γ/(2−γ))^ γ^2/(2(1−γ)) . In sharp contrast to the previous guarantee, our obtained factor ρ_γ not only strictly improves upon (1+1/γ)^−2 for every γ∈(0,1], but also can asymptotically approach the optimal (1−1/e)-approximation for submodular maximization as γ→1. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of α-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of 1−e^−γ and 1−e^−α, respectively. Here, α∈(0,1] denotes the DR ratio.
ER -