Show simple item record

dc.contributor.authorGourvès, Laurent*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorPascual, Fanny*
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2017-03-07T13:10:34Z
dc.date.available2017-03-07T13:10:34Z
dc.date.issued2017
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16294
dc.language.isoenen
dc.subjectBi-objective optimization
dc.subjectApproximation algorithm
dc.subjectMatching
dc.subject.ddc003en
dc.titleBi-objective matchings with the triangle inequality
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversité Pierre et Marie Curie (UPMC)
dc.description.abstractenThis article deals with a bi-objective matching problem. The input is a complete graph and two values on each edge (a weight and a length) which satisfy the triangle inequality. It is unlikely that every instance admits a matching with maximum weight and maximum length at the same time. Therefore, we look for a compromise solution, i.e. a matching that simultaneously approximates the best weight and the best length. For which approximation ratio ρ can we guarantee that any instance admits a ρ-approximate matching? We propose a general method which relies on the existence of an approximate matching in any graph of small size. An algorithm for computing a 1/3-approximate matching in any instance is provided. The algorithm uses an analytical result stating that every instance on at most 6 nodes must admit a 1/2-approximate matching. We extend our analysis with a computer-aided approach for larger graphs, indicating that the general method may produce a 2/5-approximate matching. We conjecture that a 1/2-approximate matching exists in any bi-objective instance satisfying the triangle inequality.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol670
dc.relation.isversionofjnldate2017
dc.relation.isversionofjnlpages1-10
dc.relation.isversionofdoi10.1016/j.tcs.2017.01.012
dc.contributor.countryeditoruniversityotherFRANCE
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-03-22T14:22:48Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds*
hal.person.labIds989*
hal.faultCode{"duplicate-entry":{"hal-01488424":{"doi":"1.0"}}}


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