A GLOBAL OPTIMIZATION METHOD FOR MINIMUM MAXIMAL FLOW PROBLEM
J. SHI, Y. YAMAMOTO
Abstract
In this paper, we present two approaches for solving an -hard problem: minimum maximal flow problem, i.e., . We introduce lower bounds on flow, and cast the problem into a minimization of a concave function over a convex set. We solve the problem by a global optimization method. As an application, we consider the minimum maximal matching problem. Some numerical experiments are also reported.