## A randomized fully polynomial-time approximation scheme for weighted perfect matching in the plane

Yasser M. Abd El-Latif , Salwa M. Ali , Hanaa A.E. Essa , Soheir M. Khamis ; Khamis, Soheir## Abstract

In the approximate Euclidean min-weighted perfect matching problem, a set V of 2n points in the plane and a real number 0 are given. Usually, a solution of this problem is a partition of points of V into n pairs such that the sum of the distances between the paired points is at most (1 ) times the optimal solution. In this paper, the authors give a randomized algorithm which follows a Monte-Carlo method. This algorithm is a randomized fully polynomial-time approximation scheme for the given problem. Fortunately, the suggested algorithm is a one tackled the matching problem in both Euclidean nonbipartite and bipartite cases. The presented algorithm outlines as follows: With repeating 1/ times, we choose a point from V to build the suitable pair satisfying the suggested condition on the distance. If this condition is achieved, then remove the points of the constructed pair from V and put this pair in M (the output set of the solution). Then, choose a point and the nearest point of it from the remaining points in V to construct a pair and put it inM . Remove the two points of the constructed pair from V and repeat this process until V becomes an empty set. Obviously, this method is very simple. Furthermore, our algorithm can be applied without any modification on complete weighted graphs m K and complete weighted bipartite graphs n n K , , where n,m 1and m is an even.

## Other data

Keywords | Perfect matching; approximation algorithm; Monte- Carlo technique; a randomized fully polynomial-time approximation scheme; and randomized algorithm |

Issue Date | 11-Nov-2012 |

Journal | (IJACSA) International Journal of Advanced Computer Science and Applications |

URI | http://research.asu.edu.eg/123456789/1118 |

DOI | 10.14569/IJACSA.2012.031122 |

File | Description | Size | Format | |
---|---|---|---|---|

A_Randomized_Fully_Polynomial-time_Approximation_Scheme_for_Weighted_Perfect_Matching_in_the_Plane (2).pdf | 402.63 kB | Adobe PDF | View/Open |

CORE Recommender

Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.