Flow-Cut Gaps for Integer and Fractional Multiflows

Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel

Consider a routing problem consisting of a demand graph H and a supply graph G. If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C…