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; 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.
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
Title | A randomized fully polynomial-time approximation scheme for weighted perfect matching in the plane | Authors | Yasser M. Abd El-Latif ; Salwa M. Ali ; Hanaa A.E. Essa; Khamis, Soheir | Keywords | Perfect matching;approximation algorithm;Monte- Carlo technique;a randomized fully polynomial-time approximation scheme;randomized algorithm | Issue Date | 11-Nov-2012 | Journal | International Journal of Advanced Computer Science and Applications (IJACSA) | DOI | 10.14569/IJACSA.2012.031122 |
Attached Files
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 |
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.