Set Function Optimization

doi:10.1007/s40305-018-0233-3

Abstract

Abstract: This article is an introduction to recent development of optimization theory on set functions, the nonsubmodular optimization, which contains two interesting results, DS (difference of submodular) functions decomposition and sandwich theorem, together with iterated sandwich method and data-dependent approximation. Some potential research problems will be mentioned.

Key words: Set function, Optimization, DS decomposition, Sandwich theorem, Iterated sandwich method

CLC Number:

90B02
90C02

Wei-Li Wu, Zhao Zhang, Ding-Zhu Du. Set Function Optimization[J]. Journal of the Operations Research Society of China, doi: 10.1007/s40305-018-0233-3.

TrendMD

References 36

[1]	Kirousis, L.M., Kranakis, E., Krizanc, D., Pelc, A.:Power consumption in packer radio networks. Theor. Comput. Sci. 243, 289-305(2000)
[2]	Chen, W.T., Huang, N.F.:The strongly connection problem on multihop packet radio networks. IEEE Trans. Commun. 37(3), 293-295(1989)
[3]	Pruhs, K.:Speed scaling. In:Encyclopedia of Algorithms, pp. 2045-2047(2016)
[4]	Edmonds, J., Pruhs, K.:Scalably scheduling processes with arbitrary speedup curves. ACM Trans. Algorithms 8(3), 28(2012)
[5]	Lin, H., Bilmes, J.:Optimal selection of limited vocabulary speech corpora. In:Interspeech (2011)
[6]	Iyer, R.K., Jegelka, S., Bilmes, J.A.:Fast semidifferential-based submodular function optimization. ICML 3, 855-863(2013)
[7]	Nagano, K., Kawahara, Y., Aihara, K.:Size-constrained submodular minimization through minimum norm base. In:Proceedings of the 28th International Conference on Machine Learning, Bellevue, WA, USA (2011)
[8]	Barhan, A., Shakhomirov, A.:Methods for sentiment analysis of Twitter messages. In:Proceeding of the 12th Conference of Fruct Association, pp. 216-222(2012)
[9]	Wu, B., Lyu, S., Ghanem, B.:Constrained submodular minimization for missing labels and class imbalance in multi-label learning. In:The Thirtieth AAAI Conference on Artificial Intelligence, pp. 2229-2236(2016)
[10]	Grötschel, M., Lovász, L., Schrijver, A.:Geometric Algorithms and Combinatorial Optimization, 2nd edn. Springer, Berlin (1988)
[11]	Orlin, J.B.:A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. 118, 237-251(2009)
[12]	Schrijver, A.:A combinatorial algorithm minimizing submodular functions in strong polynomial time. J. Comb. Theory (B) 80, 346-355(2000)
[13]	Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.:An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265-294(1978)
[14]	Sviridenko, M.:A note on maximizing a submodular set function subject to knapsack constraint. Oper. Res. Lett. 32, 41-43(2004)
[15]	Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N.:Cost-effective outbreak detection in networks. In:KDD'07:Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, pp. 420-429. ACM (2007)
[16]	Calinescu, G., Chekuri, C., Pl, M., Vondrk, J.:Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740-1766(2011)
[17]	Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.:An analysis of approximations for maximizing submodular set functions-Ⅱ. In:Polyhedral Combinatorics. Springer, Berlin, Heidelberg (1978)
[18]	Wolsey, A.L.:An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385-393(1982)
[19]	Feige, U., Mirrokni, V., Vondrak, J.:Maximizing nonmonotone submodular functions. In:Proceedings of the IEEE Foundations of Computer Science, pp. 461-471(2007)
[20]	Lee, J., Mirrokni, V., Nagarajan, V., Sviridenko, M.:Nonmonotone submodular maximization under matroid and knapsack constraints. In:Proceedings of the ACM Symposium on Theory of Computing, pp. 323-332(2009)
[21]	Feldman, M., Naor, J., Schwartz, R.:A unified continuous greedy algorithm for submodular maximization. In:IEEE FOCS, pp. 570-579(2011)
[22]	Svitkina, Z., Fleischer, L.:Submodular approximation:sampling-based algorithms and lower bounds. SIAM J. Comput. 40, 1715-1737(2011)
[23]	Feige, U., Izsak, R.:Welfare maximization and the supermodular degree. In:Conference on Innovations in Theoretical Computer Science. ACM, pp. 247-256(2013)
[24]	Feldman, M., Izsak, R.:Constrained monotone function maximization and the supermodular degree. (2014). arXiv:1407.6328
[25]	Narasimhan, M., Bilmes, J.:A submodular-supermodular procedure with applications to discriminative structure learning. In:The Twenty-First Conference on Uncertainty in Artificial Intelligence (2005)
[26]	Iyer, R., Bilmes, J.:Algorithms for approximate minimization of the difference between submodular functions. In:Twenty-eighth Conference on Uncertainty in Artificial Intelligence (2012)
[27]	Iyer, R., Bilmes, J.:Submodular optimization subject to submodular cover and submodular knapsack constraints. In:Advances of NIPS (2013). arXiv:1311.2106
[28]	Wu, C.,Wang, Y., Lu, Z., Pardalos, P.M., Xu, D., Zhang, Z., Du, D.-Z.:Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming. Math. Program. 169(1), 255-275(2018)
[29]	Maehara, T., Murota, K.:A framework of discrete DC programming by discrete convex analysis. Math. Program. 152(1-2), 435-466(2015)
[30]	Cunningham, W.H.:Decomposition of submodular functions. Combinatorica 3(1), 53C68(1983)
[31]	Zhu, Y., Lu, Z., Bi, Y., Wu, W., Jiang, Y., Li, D.:Influence and profit:two sides of the coin. In:ICDM, pp. 1301-1306(2013)
[32]	Fujishige, S.:Submodular Functions and Optimization, vol. 58. Elsevier Science, Amsterdam (2005)
[33]	Wei, L., Chen, W., Lakshmanan, L.V.S.:From competition to complementarity:comparative influence diffusion and maximization. Proc. VLDB Endow. 9(2), 60-71(2015)
[34]	Chen, W., Lin, T., Tan, Z., Zhao, M., Zhou, X.:Robus Influence Maximization, KDD'16. San Francisco, CA, USA (2016)
[35]	Wang, Z., Yang, Y., Pei, J., Chen, E.:Activity maximization by effective information diffusion in social networks (2016). arXiv:1610.07754v1[cs.SI]
[36]	Zhu, J., Zhu, J., Ghosh, S., Wu, W., Yuan, J.:Social influence maximization in hypergraph in social networks. IEEE Trans. Netw. Sci. Eng. (2018). https://doi.org/10.1109/TNSE.2018.2873759