In the minimization of the number of subtours made by the insertion head of an SMD placement machine a variant of the network flow problem arose. In a network with n vertices and m arcs a set F of arcs (parametrized arcs) is given. The task is to find a flow of a given size such that the maximum of flow values along the arcs from F is minimized. This problem can be solved by a sequence of maximum flow computations in modified networks where the capacities of the parametrized arcs are successively set to an increasing sequence of target parameter values. We show that it suffices to consider at most O(|F|) different target values and so this approach leads to a strongly polynomial algorithm consisting of at most O(|F|) maximum flow computations.
algorithm, SMD machine optimization, network flow
90B30, 90C27, 05C21