Trader multiflow and box-TDI systems in series-parallel graphs

作     者：Cornaz, Denis Grappe, Roland Lacroix, Mathieu 

作者机构：Univ Paris 09 Pl Marechal Lattre Tassigny F-75775 Paris 16 France Univ Paris 13 Sorbonne Paris Cite LIPN CNRS UMR 7030 F-93430 Villetaneuse France 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2019年第31卷

页      面：103-114页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：The very careful reading of the paper by an anonymous referee has allowed an improvement of several technical proofs readability  we would like to thank her or him very much 

主　　题：Box-TDI system Series-parallel graph Multiflow 

摘      要：Series-parallel graphs are known to be precisely the graphs for which the standard linear systems describing the cut cone, the cycle cone, the T-join polytope, the cut polytope, the multicut polytope and the T-join dominant are TDI. We prove that these systems are actually box-TDI. As a byproduct, our result yields a min-max relation for a new problem: the trader multiflow problem. The latter generalizes both the maximum multiflow and min-cost multiflow problems and we show that it is polynomial-time solvable in series-parallel graphs. (C) 2018 Elsevier B.V. All rights reserved.