DETERMINISTIC (1/2+e)-APPROXIMATION FOR SUBMODULAR MAXIMIZATION OVER A MATROID
arxiv(2023)
摘要
We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2+e)-approximation for the problem (for some \varepsilon \geq 8 \cdot 10 -4). This algorithm is the first deterministic algorithm known to improve over the 1/2-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsey, and Fisher in 1978.
更多查看译文
关键词
submodular optimization, matroid, deterministic algorithms
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要