A note on the hardness results for the labeled perfect matching problems in bipartite graphs

Jérôme Monnot

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 3, page 315-324
  • ISSN: 0399-0559

Abstract

top
In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (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.

How to cite

top

Monnot, Jérôme. "A note on the hardness results for the labeled perfect matching problems in bipartite graphs." RAIRO - Operations Research 42.3 (2008): 315-324. <http://eudml.org/doc/250426>.

@article{Monnot2008,
abstract = { In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (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. },
author = {Monnot, Jérôme},
journal = {RAIRO - Operations Research},
keywords = {Labeled matching; bipartite graphs; approximation and complexity; inapproximation bounds.; labeled matching; approximation and complexity; inapproximation bounds},
language = {eng},
month = {8},
number = {3},
pages = {315-324},
publisher = {EDP Sciences},
title = {A note on the hardness results for the labeled perfect matching problems in bipartite graphs},
url = {http://eudml.org/doc/250426},
volume = {42},
year = {2008},
}

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
DA - 2008/8//
PB - EDP Sciences
VL - 42
IS - 3
SP - 315
EP - 324
AB - In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (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.
LA - eng
KW - Labeled matching; bipartite graphs; approximation and complexity; inapproximation bounds.; labeled matching; approximation and complexity; inapproximation bounds
UR - http://eudml.org/doc/250426
ER -

References

top
  1. P. Alimonti and V. Kann, Hardness of approximating problems on cubic graphs, in Proc. CIAC'97, Lect. Notes Comput. Sci.1203 (1997) 288–298.  
  2. S. Arora and M. Sudan, Improved low-degree testing and its applications. Combinatorica23 (2003) 365–426.  Zbl1101.68572
  3. K. Cameron, Coloured matchings in bipartite graphs. Discrete Math.169 (1997) 205–209.  Zbl0880.05070
  4. M. Costa, D. de Werra, C. Picouleau and B. Ries, Bicolored matchings in some classes of graphs. Graphs Comb.23 (2007) 47–60.  Zbl1116.05062
  5. A. Itai, M. Rodeh and S. Tanimoto, Some matching problems in bipartite graphs. J. ACM25 (1978) 517–525.  Zbl0388.68059
  6. J. Monnot, On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems, in Proc. ISAAC'05, Lect. Notes Comput. Sci.3827 (2005) 934–943.  Zbl1175.68203
  7. J. Monnot, The Labeled perfect matching in bipartite graphs. Inf. Proc. Lett.96 (2005) 81–88.  Zbl1191.68470
  8. A. Paz and S. Moran, Non deterministic polynomial optimisation problems and their approximation, Theor. Comput. Sci.95 (1981) 251–277.  Zbl0459.68015
  9. M.B. Richey and A.P. Punnen, Minimum Perfect Bipartite Matchings and Spanning Trees under Categorization. Discrete Appl. Math.39 (1992) 147–153.  Zbl0776.05088

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.