Improved Lower Bounds on Multiflow-Multicut Gaps

Sina Kalantarzadeh, Nikhil Kumar

Given a set of source-sink pairs, the maximum multiflow problem asks for the maximum total amount of flow that can be feasibly routed between them. The minimum multicut, a dual pro…