Trader multiflow and box-TDI systems in series-parallel graphs
hal.structure.identifier | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE] | |
dc.contributor.author | Cornaz, Denis | |
hal.structure.identifier | Laboratoire d'Informatique de Paris-Nord [LIPN] | |
dc.contributor.author | Grappe, Roland | |
hal.structure.identifier | Laboratoire d'Informatique de Paris-Nord [LIPN] | |
dc.contributor.author | Lacroix, Mathieu
HAL ID: 741352 ORCID: 0000-0001-8385-3890 | |
dc.date.accessioned | 2019-07-17T10:34:09Z | |
dc.date.available | 2019-07-17T10:34:09Z | |
dc.date.issued | 2019 | |
dc.identifier.issn | 1572-5286 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/19250 | |
dc.language.iso | en | en |
dc.subject | Box-TDI system | en |
dc.subject | Series–parallel graph | en |
dc.subject | Multiflow | en |
dc.subject.ddc | 518 | en |
dc.title | Trader multiflow and box-TDI systems in series-parallel graphs | en |
dc.type | Article accepté pour publication ou publié | |
dc.description.abstracten | 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. | en |
dc.relation.isversionofjnlname | Discrete Optimization | |
dc.relation.isversionofjnlvol | 31 | en |
dc.relation.isversionofjnlissue | 1 | en |
dc.relation.isversionofjnldate | 2019-02 | |
dc.relation.isversionofjnlpages | 103-114 | en |
dc.relation.isversionofdoi | 10.1016/j.disopt.2018.09.003 | en |
dc.relation.isversionofjnlpublisher | Elsevier | en |
dc.subject.ddclabel | Modèles mathématiques. Algorithmes | en |
dc.relation.forthcoming | non | en |
dc.relation.forthcomingprint | non | en |
dc.description.ssrncandidate | non | en |
dc.description.halcandidate | oui | en |
dc.description.readership | recherche | en |
dc.description.audience | International | en |
dc.relation.Isversionofjnlpeerreviewed | oui | en |
dc.relation.Isversionofjnlpeerreviewed | oui | en |
dc.date.updated | 2019-07-17T10:32:10Z | |
hal.identifier | hal-02186541 | * |
hal.version | 1 | * |
hal.author.function | aut | |
hal.author.function | aut | |
hal.author.function | aut |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |