Submodular function maximization over graphs via zero-suppressed binary decision diagrams
Article No.: 174, Pages 1422 - 1430
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.
References
[1]
Bergman, D.; Cire, A.; van Hoeve, W.-J.; and Hooker, J. 2016. Decision Diagrams for Optimization. Springer, first edition.
[2]
Bishop, C. M. 2006. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag, New York.
[3]
Buchbinder, N.; Feldman, M.; Seffi, J.; and Schwartz, R. 2015. A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5):1384-1402.
[4]
Chekuri, C., and Pal, M. 2005. A recursive greedy algorithm for walks in directed graphs. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 245-253. IEEE.
[5]
Chen, W.; Chen, Y.; and Weinberger, K. 2015. Filtered search for submodular maximization with controllable approximation bounds. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, volume 38, 156-164. PMLR.
[6]
Conforti, M., and Cornuíjols, G. 1984. Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3):251-274.
[7]
Coudert, O. 1997. Solving graph optimization problems with ZBDDs. In Proceedings of European Conference on Design and Test, 224. IEEE.
[8]
Garg, N.; Santosh, V. S.; and Singla, A. 1993. Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 103-111. SIAM.
[9]
Heeger, K., and Vygen, J. 2016. Two-connected spanning subgraphs with at most 10/7 OPT edges. arXiv preprint arXiv:1609.00147.
[10]
Inoue, Y., and Minato, S. 2016. Acceleration of ZDD construction for subgraph enumeration via path-width optimization. Technical report, TCS-TR-A-16-80, Hokkaido University.
[11]
Kawahara, J.; Inoue, T.; Iwashita, H.; and Minato, S. 2017a. Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A(9):1773-1784.
[12]
Kawahara, J.; Saitoh, T.; Suzuki, H.; and Yoshinaka, R. 2017b. Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs. In Proceedings of Computational Intelligence in Information Systems Conference, 294-305. Springer International Publishing.
[13]
Ke, W. C.; Liu, B. H.; and Tsai, M. J. 2011. Efficient algorithm for constructing minimum size wireless sensor networks to fully cover critical square grids. IEEE Trans. Wireless Commun. 10(4):1154-1164.
[14]
Knuth, D. E. 2011. The Art of Computer Programming: Combinatorial Algorithms, Part 1, volume 4A. Addison-Wesley Professional, 1st edition.
[15]
Krause, A.; Guestrin, C.; Gupta, A.; and Kleinberg, J. 2006. Near-optimal sensor placements: Maximizing information while minimizing communication cost. In Proceedings of the 5th International Conference on Information Processing in Sensor Networks, 2-10. ACM.
[16]
Krause, A.; McMahan, H. B.; Guestrin, C.; and Gupta, A. 2008. Robust submodular observation selection. J. Mach. Learn. Res. 9(Dec):2761-2801.
[17]
Krause, A.; Singh, A.; and Guestrin, C. 2008. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9(Feb):235-284.
[18]
Lin, H., and Bilmes, J. 2010. Multi-document summarization via budgeted maximization of submodular functions. In Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 912-920.
[19]
Liu, X.; Xiao, L.; Kreling, A.; and Liu, Y. 2006. Optimizing overlay topology by reducing cut vertices. In Proceedings of the 2006 International Workshop on Network and Operating Systems Support for Digital Audio and Video, 17:1-17:6. ACM.
[20]
Madden, S. 2004. Intel Lab Data. http://db.csail.mit.edu/labdata/labdata.html. Last accessed 30 November 2016.
[21]
Maehara, T.; Kawase, Y.; Sumita, H.; Tono, K.; and Kawarabayashi, K. 2017. Optimal pricing for submodular valuations with bounded curvature. In Proceedings of the 31st AAAI Conference on Artificial Intelligence.
[22]
Minato, S. 1993. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the 30th International Design Automation Conference, 272-277. IEEE.
[23]
Morrison, D. R.; Sewell, E. C.; and Jacobson, S. H. 2016. Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. INFORMS J. Comput. 28(1):67-82.
[24]
Nemhauser, G. L.; Wolsey, L. A.; and Fisher, M. L. 1978. An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1):265-294.
[25]
Sedgewick, R., and Wayne, K. 2011. Algorithms, 4th Edition. Addison-Wesley.
[26]
Sharma, D.; Kapoor, A.; and Deshpande, A. 2015. On greedy maximization of entropy. In Proceedings of the 32nd International Conference on Machine Learning, 1330-1338.
[27]
Singh, A.; Krause, A.; Guestrin, C.; and Kaiser, W. J. 2009. Efficient informative sensing using multiple robots. J. Artif. Int. Res. 34(1):707-755.
[28]
Suzuki, H., and Minato, S. 2016. Adding the vertex indices for enumerating and indexing the graphs via ZDD (in Japanese). Special Interest Group on Fundamental Problems in Artificial Intelligence 101:41-46.
[29]
Suzuki, H. 2016. Frontier based search with vertex indices. https://github.com/hs-nazuna/FrontierBasedSearchWithVertexIndices. Last accessed 1 September 2017.
[30]
Sviridenko, M. 2004. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1):41-43.
[31]
Thoma, M.; Cheng, H.; Gretton, A.; Han, J.; Kriegel, H.-P.; Smola, A.; Song, L.; Yu, P. S.; Yan, X.; and Borgwardt, K. 2009. Near-optimal supervised feature selection among frequent subgraphs. In Proceedings of the 2009 SIAM International Conference on Data Mining, 1076-1087.
[32]
Xiong, S., and Li, J. 2010. An efficient algorithm for cut vertex detection in wireless sensor networks. In Proceedings of the 30th International Conference on Distributed Computing Systems, 368-377. IEEE.
[33]
Zeng, Y.; Chen, X.; Cao, X.; Qin, S.; Cavazza, M.; and Xiang, Y. 2015. Optimal route search with the coverage of users' preferences. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, 2118-2124.
[34]
Zhang, H., and Vorobeychik, Y. 2016. Submodular optimization with routing constraints. In Proceedings of the 30th AAAI Conference on Artificial Intelligence.
[35]
Zheng, Y.; Liu, F.; and Hsieh, H.-P. 2013. U-Air: when urban air quality inference meets big data. In Proceedings of the 19th SIGKDD International Conference on Knowledge Discovery and Data Mining, 1436-1444. ACM.
Index Terms
- Submodular function maximization over graphs via zero-suppressed binary decision diagrams
Index terms have been assigned to the content through auto-classification.
Recommendations
Encoding CSPs with Zero-Suppressed Decision Diagrams
ICTAI '08: Proceedings of the 2008 20th IEEE International Conference on Tools with Artificial Intelligence - Volume 01A well established technology in the knowledge compilationcommunity is the encoding of constraint satisfaction problems (CSPs) by binary decision diagrams (BDDs). Atechnology that among other things has found its use interactive configuration and other ...
Improved Randomized Algorithm for k-Submodular Function Maximization
Submodularity is one of the most important properties in combinatorial optimization, and $k$-submodularity is a generalization of submodularity. Maximization of a $k$-submodular function requires an exponential number of value oracle queries, and ...
Chain Reduction for Binary and Zero-Suppressed Decision Diagrams
AbstractChain reduction enables reduced ordered binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) to each take advantage of the other’s ability to symbolically represent Boolean functions in compact form. For any Boolean ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2018 Association for the Advancement of Artificial Intelligence.
Sponsors
- Association for the Advancement of Artificial Intelligence
Publisher
AAAI Press
Publication History
Published: 02 February 2018
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 44Total Downloads
- Downloads (Last 12 months)39
- Downloads (Last 6 weeks)11
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in