Show simple item record

dc.contributor.authorBaïou, Mourad
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2010-04-12T08:23:36Z
dc.date.available2010-04-12T08:23:36Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3915
dc.language.isoenen
dc.subjectPolyhedral combinatoricsen
dc.subjectPolytopesen
dc.subjectTraveling salesman problemen
dc.subject.ddc003en
dc.titleThe Steiner Traveling Salesman Polytope and Related Polyhedraen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper we consider an extended formulation of the Steiner traveling salesman problem, that is, when variables are associated with both the edges and the nodes of the graph. We give a complete linear description of the associated polytope when the underlying graph is series-parallel. By projecting this polytope onto the edge variables, we obtain a characterization of the Steiner traveling salesman polytope in the same class of graphs. Both descriptions yield polynomial time (cutting plane) algorithms for the corresponding problems in that class of graphs.en
dc.relation.isversionofjnlnameSIAM Journal on Optimization
dc.relation.isversionofjnlvol13en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2002
dc.relation.isversionofjnlpages498-507en
dc.relation.isversionofdoihttp://dx.doi.org/10.1137/S1052623400322287en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSIAMen
dc.subject.ddclabelRecherche opérationnelleen


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