Show simple item record

Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2010-03-22T11:08:17Z
dc.date.available2010-03-22T11:08:17Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3743
dc.language.isoenen
dc.subjectHamiltonian pathsen
dc.subjectAnalysis of algorithmsen
dc.subjectperformance ratioen
dc.subjectCombinatorial optimizationen
dc.subjectComplexity theoryen
dc.subjectdifferential ratioen
dc.subjectApproximate algorithmsen
dc.subject.ddc003en
dc.titleApproximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)en
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis paper deals with the problem of constructing Hamiltonian paths of optimal weight, called HPPs,t if the two endpoints are specified, HPPs if only one endpoint is specified. We show that HPPs,t is Image -differential approximable and HPPs is Image -differential approximable. Moreover, we observe that these problems cannot be differential approximable better than Image . Based upon these results, we obtain new bounds for standard ratio: a Image -standard approximation for MImage HPPs,t and a Image for MImage HPPs, which can be improved to Image for MImage HPPs,t[a,2a] (all the edge weights are within an interval [a,2a]), to Image for MImage HPPs[a,2a] and to Image for MImage HPPs,t[a,2a], to Image for MImage HPPs[a,2a].en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol161en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2005-03
dc.relation.isversionofjnlpages721-735en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2003.09.007en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail
Name:
publi113.pdf
Size:
323.1Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record