TY - JOUR
AU - Sakaue, Shinsaku
AU - Nishino, Masaaki
AU - Yasuda, Norihito
PY - 2018/04/25
Y2 - 2023/03/29
TI - Submodular Function Maximization Over Graphs via Zero-Suppressed Binary Decision Diagrams
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 32
IS - 1
SE - AAAI Technical Track: Heuristic Search and Optimization
DO - 10.1609/aaai.v32i1.11520
UR - https://ojs.aaai.org/index.php/AAAI/article/view/11520
SP -
AB - <p> Submodular function maximization (SFM) has attracted much attention thanks to its applicability to various practical problems. Although most studies have considered SFM with size or budget constraints, more complex constraints often appear in practice. In this paper, we consider a very general class of SFM with such complex constraints (e.g., an s-t path constraint on a given graph). We propose a novel algorithm that takes advantage of zero-suppressed binary decision diagrams, which store all feasible solutions efficiently thus enabling us to circumvent the difficulty of determining feasibility. Theoretically, our algorithm is guaranteed to achieve (1-c)-approximations, where c is the curvature of a submodular function. Experiments show that our algorithm runs much faster than exact algorithms and finds better solutions than those obtained by an existing approximation algorithm in many instances. Notably, our algorithm achieves better than a 90%-approximation in all instances for which optimal values are available. </p>
ER -