Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2020-05-15T15:31:36Z
dc.date.available2020-05-15T15:31:36Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20749
dc.language.isoenen
dc.subjectlabeled matching
dc.subjectbipartite graphs
dc.subjectApproximation and complexity
dc.subjectinapproximation bounds
dc.subject.ddc003en
dc.titleA note on the hardness results for the labeled perfect matching problems in bipartite graphs
dc.typeDocument de travail / Working paper
dc.description.abstractenIn this note, we strengthen the inapproximation bound of O(log n) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters 96 (2005) 81-88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected planar cubic bipartite graphs.
dc.publisher.cityParisen
dc.relation.ispartofseriestitleCahier du LAMSADE
dc.relation.ispartofseriesnumber256
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00917833
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-09-25T16:02:31Z


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