Multiflows and metrics

点击翻译按钮获取中文摘要

We studied multiflow problems in combinatorial optimization. We introduced and developed the tight-span duality theory, which extends the duality relationship between multiflows and metrics, a well-known duality since 70's. As a consequence, We solved Karzanov' s problem, one of important open problems in the literature, which asks a complete characterization for the class of multiflow problems admitting combinatorial min-max theorems and the discreteness of flows. This result is an important step toward a unified theory for multiflow problems.