A NEW MIN-CUT MAX-FLOW RATIO FOR MULTICOMMODITY FLOWS

摘要

In this paper we present a new bound on the min-cut max-flow ratio for multicom-modity flow problems with specified demands. For multicommodity flows, this is a generalization of the well-known relationship between the capacity of a minimum cut and the va