Nonlinear combinatorial optimization (Q1738339)

Combinatorial optimization is a very popular research field that has a rich theory and is useful for a lot of real world applications. There exist several good books on this topic. One of the most extensive ones is [\textit{A. Schrijver}, Combinatorial optimization. Polyhedra and efficiency (3 volumes). Berlin: Springer (2003; Zbl 1041.90001)], which covers most of the topics in combinatorial optimization up to its publication year 2003. A combinatorial optimization problem consists of maximizing or minimizing a linear function over a finite set of objects. The difficulty arises from the fact that the ground set grows exponentially. For such a problem one tries to design an efficient algorithm, where efficient means polynomial time solvable. Some problems probably do not admit a polynomial time algorithm. In this case researchers design approximation algorithms or heuristics and try to show that no polynomial time algorithm for this problem can exist. In real world applications linear functions are not always sufficient. Thus, more and more interest in optimizing nonlinear functions in combinatorial optimization problems arose. In this book several techniques and their applications are discussed. It consists of 16 independent chapters. Each chapter can be read by its own and does not assume knowledge from one of the other chapters. It is not intended as an introductory text book on nonlinear combinatorial optimization, thus basic knowledge in combinatorial optimization and nonlinear optimization is assumed. The book introduces several methods used in nonlinear combinatorial optimization as for example submodular functions, polymatroids and a discrete variant of Newton's method. It also contains several chapters on applications of these methods in social network studies, multi-document summarization, and viral marketing. Furthermore, the chapter ``Solving Combinatorial Problems with Machine Learning Methods'' shows how combinatorial problems can be solved using non-linear methods. However, for readers familiar with linear integer programming, the models solved there seem to be quite small. All in all, the book ``Nonlinear combinatorial optimization'' introduces some interesting topics in this relatively new field. The articles of this volume will be announced individually. Indexed articles: \textit{Zhang, Zhao; Huang, Xiaohui}, A role of minimum spanning tree, 1-35 [Zbl 1487.90631] \textit{Zhang, Zhao; Huang, Xiaohui}, Discrete Newton method, 37-56 [Zbl 1487.90578] \textit{Du, Donglei; Han, Qiaoming; Wu, Chenchen}, An overview of submodular optimization: single- and multi-objectives, 57-79 [Zbl 1487.90548] \textit{Cao, Shengyu; He, Simai}, Discrete convex optimization and applications in supply chain management, 81-121 [Zbl 1487.90543] \textit{Yang, Ruiqi; Xu, Dachuan; Li, Min; Xu, Yicheng}, Thresholding methods for streaming submodular maximization with a cardinality constraint and its variants, 123-140 [Zbl 1487.90577] \textit{Wu, Weili; Zhang, Zhao; Du, Ding-Zhu}, Nonsubmodular optimization, 141-152 [Zbl 1487.90575] \textit{Chen, Lin}, On block-structured integer programming and its applications, 153-177 [Zbl 1487.90481] \textit{Huang, Zhiyi}, Online combinatorial optimization problems with non-linear objectives, 179-205 [Zbl 1487.90554] \textit{Guo, Tiande; Han, Congying; Tang, Siqi; Ding, Man}, Solving combinatorial problems with machine learning methods, 207-229 [Zbl 1487.90551] \textit{He, Zaobo; Lin, Yaguang; Liang, Yi; Wang, Xiaoming; Vera Venkata Sai, Akshita Maradapu; Cai, Zhipeng}, Modeling malware propagation dynamics and developing prevention methods in wireless sensor networks, 231-250 [Zbl 1487.90208] \textit{Ghosh, Smita; Zhu, Jianming; Wu, Weili}, Composed influence maximization in social networks, 251-264 [Zbl 1487.91095] \textit{Gu, Shuyang; Du, Hongwei; Thai, My T.; Du, Ding-Zhu}, Friending, 265-272 [Zbl 1487.91097] \textit{Li, Yi; Yan, Ruidong; Wu, Weili}, Optimization on content spread in social network studies, 273-284 [Zbl 1487.91100] \textit{Gu, Shuyang; Gao, Chuangen; Wu, Weili}, Interaction-aware influence maximization in social networks, 285-294 [Zbl 1487.91098] \textit{Satpute, Meghana N.; Dong, Luobing; Wu, Weili; Du, Ding-Zhu}, Multi-document extractive summarization as a non-linear combinatorial optimization problem, 295-308 [Zbl 1487.90569] \textit{Guo, Jianxiong; Wu, Weili}, Viral marketing for complementary products, 309-315 [Zbl 1487.90410]