Submodular Function Maximization Over Graphs via Zero-Suppressed Binary Decision Diagrams

Authors

  • Shinsaku Sakaue Nippon Telegraph and Telephone Corporation
  • Masaaki Nishino Nippon Telegraph and Telephone Corporation
  • Norihito Yasuda Nippon Telegraph and Telephone Corporation

Keywords:

submodular function, graph, zero-suppressed binary decision diagram

Abstract

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.

Downloads

Published

2018-04-25

How to Cite

Sakaue, S., Nishino, M., & Yasuda, N. (2018). Submodular Function Maximization Over Graphs via Zero-Suppressed Binary Decision Diagrams. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11520

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization