Non-static network optimization problems: A survey (Q2735078)

The authors provide a survey of papers on non-static network optimization problems. In doing so they give the classification of such problems on non-static shortest path problems, non-static maximum cost flow problems, non-static minimum cost flow problems, and non-static vehicle routing problems. Besides some more specific non-static network optimization problems that do not fall into any of the above categories are shortly mentioned, e.g., the minimum spanning tree problem, and others. For every category, the static form is also shortly mentioned. Besides, it is argued that almost all static problems are solvable in polynomial time, but many non-static problems are NP-complete. The review gives only a verbal description of non-static network optimization problems. It does not carry out any concrete algorithm for a solution of such problems. Therefore it is not clear why the authors often mention that there are good convergent algorithms to solve also NP-hard problems of the above mentioned type.NEWLINENEWLINEFor the entire collection see [Zbl 0962.00004].