Show simple item record

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

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorCornaz, Denis
hal.structure.identifierLaboratoire d'Informatique de Paris-Nord [LIPN]
dc.contributor.authorGrappe, Roland
hal.structure.identifierLaboratoire d'Informatique de Paris-Nord [LIPN]
dc.contributor.authorLacroix, Mathieu
HAL ID: 741352
ORCID: 0000-0001-8385-3890
dc.date.accessioned2019-07-17T10:34:09Z
dc.date.available2019-07-17T10:34:09Z
dc.date.issued2019
dc.identifier.issn1572-5286
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19250
dc.language.isoenen
dc.subjectBox-TDI systemen
dc.subjectSeries–parallel graphen
dc.subjectMultiflowen
dc.subject.ddc518en
dc.titleTrader multiflow and box-TDI systems in series-parallel graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenSeries–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.isversionofjnlnameDiscrete Optimization
dc.relation.isversionofjnlvol31en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2019-02
dc.relation.isversionofjnlpages103-114en
dc.relation.isversionofdoi10.1016/j.disopt.2018.09.003en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelModèles mathématiques. Algorithmesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-07-17T10:32:10Z
hal.identifierhal-02186541*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record