This paper presents a faster algorithm for the M-convex submodular How problem, which is a generalization of the minimum-cost How problem with an M-convex cost function for the How-boundary, where an M-convex function is a nonlinear nonseparable cliserete convex function on integer points. The algorithm extends the capacity sealing approach lor the submodular How problem by Fleischer. Iwata and MeCormiek (2002) with the aid of a novel technique of changing the potential by solving maximum submodular How problems.

Скачать книгу бесплатно (pdf, 229 Kb)

---

Читать «A capacity scaling algorithm for M-convex submodular flow»