Voir la notice de l'article provenant de la source Numdam
In this note, we strengthen the inapproximation bound of 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.
@article{RO_2008__42_3_315_0,
author = {Monnot, J\'er\^ome},
title = {A note on the hardness results for the labeled perfect matching problems in bipartite graphs},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {315--324},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
year = {2008},
doi = {10.1051/ro:2008020},
mrnumber = {2444490},
zbl = {1157.68053},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2008020/}
}
TY - JOUR AU - Monnot, Jérôme TI - A note on the hardness results for the labeled perfect matching problems in bipartite graphs JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 315 EP - 324 VL - 42 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2008020/ DO - 10.1051/ro:2008020 LA - en ID - RO_2008__42_3_315_0 ER -
%0 Journal Article %A Monnot, Jérôme %T A note on the hardness results for the labeled perfect matching problems in bipartite graphs %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 315-324 %V 42 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2008020/ %R 10.1051/ro:2008020 %G en %F RO_2008__42_3_315_0
Monnot, Jérôme. A note on the hardness results for the labeled perfect matching problems in bipartite graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 315-324. doi: 10.1051/ro:2008020
Cité par Sources :