Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-12T13:45:58Z
dc.date.available2010-01-12T13:45:58Z
dc.date.issued2003
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2894
dc.language.isoenen
dc.subjectComplexityen
dc.subjectAlgorithmsen
dc.subjectAlgorithmical approximationen
dc.subject.ddc003en
dc.titleDifferential approximation results for the Steiner tree problemen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherESSEC;France
dc.description.abstractenWe study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than |V N−ε for any ε ε (0, 1), where V and N are the vertex-set of the input graph and the set of terminal vertices, respectively. For the second of the Steiner tree versions considered, the one where the input graph is supposed complete and the edge distances are arbitrary, we prove that it can be differentially approximated within 1/2. For the third one defined on complete graphs with edge distances 1 or 2, we show that it is differentially approximable within 0.82. Also, extending the result of Bern and Plassmann [1], we show that the Steiner tree problem with edge lengths 1 and 2 is MaxSNP-complete even in the case where IVY less-than-or-equals, slant rINI, for any r > 0. This allows us to finally show that the Steiner tree problem with edge lengths 1 and 2 cannot by approximated by polynomial time differential approximation schemata.en
dc.relation.isversionofjnlnameApplied Mathematics Letters
dc.relation.isversionofjnlvol16en
dc.relation.isversionofjnlissue5en
dc.relation.isversionofjnldate2003
dc.relation.isversionofjnlpages733-739en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0893-9659(03)00075-2en
dc.description.sponsorshipprivatenonen
dc.relation.isversionofjnlpublisherElsevieren
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