dc.contributor.author Gourvès, Laurent * dc.contributor.author Monnot, Jérôme * dc.contributor.author Pascual, Fanny * dc.contributor.author Vanderpooten, Daniel * dc.date.accessioned 2017-03-07T13:10:34Z dc.date.available 2017-03-07T13:10:34Z dc.date.issued 2017 dc.identifier.issn 0304-3975 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/16294 dc.language.iso en en dc.subject Bi-objective optimization dc.subject Approximation algorithm dc.subject Matching dc.subject.ddc 003 en dc.title Bi-objective matchings with the triangle inequality dc.type Article accepté pour publication ou publié dc.contributor.editoruniversityother Université Pierre et Marie Curie (UPMC) dc.description.abstracten This 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.isversionofjnlname Theoretical Computer Science dc.relation.isversionofjnlvol 670 dc.relation.isversionofjnldate 2017 dc.relation.isversionofjnlpages 1-10 dc.relation.isversionofdoi 10.1016/j.tcs.2017.01.012 dc.contributor.countryeditoruniversityother FRANCE dc.relation.isversionofjnlpublisher Elsevier dc.subject.ddclabel Recherche opérationnelle en dc.description.ssrncandidate non dc.description.halcandidate oui dc.description.readership recherche dc.description.audience International dc.relation.Isversionofjnlpeerreviewed oui dc.date.updated 2017-03-22T14:22:48Z hal.person.labIds 989 * hal.person.labIds 989 * hal.person.labIds * hal.person.labIds 989 * hal.faultCode {"duplicate-entry":{"hal-01488424":{"doi":"1.0"}}}
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.