Given two point sets S and T, we first study the many-to-many matching with demands problem (MMDproblem) where each point of one set must be matched to  a given number of the points of the other set. We propose an O(n^2) time algorithm for computing a one-dimensional MMD (OMMD) of minimum cost  where |S|+|T| = n. In an OMMD  the input point sets S and T lie on the  line and the cost of matching a point to another point is equal to the distance between the two points. Then, we study a generalized version of  MMD problem, the many-to-many matching with demands and capacities problem (MMDC)  , that in which each point has a limited capacity in addition to a demand. We give an O(n^2) time algorithm for the minimum cost one dimensional MMDC  problem.
Given two point sets S and T, we first study the many-to-many matching with demands (MMD) problem, where each point of one set must be matched to at least a given number of the points of the other set. We propose an O(n^2) time algorithm for computing a one dimensional MMD (OMMD) of minimum cost , where |S|+|T| = n. In an OMMD problem, the input point sets S and T lie on the real line and the cost of matching a point to another point is equal to the distance between the two points. We also study a generalized version of the MMD problem, the many-to-many matching with demands and capacities (MMDC) problem , that in which each point has a limited capacity in addition to a demand. We give an O(n^2) time algorithm for the minimum-cost one dimensional MMDC (OMMDC) problem.
R
problem (MMDproblem)
(MMD) problem,
A
at least
R
one-dimensional
one dimensional
A
,
A
problem,
A
real
R
Then, we
We also
A
the
D
problem
A
problem
R
minimum cost
minimum-cost
A
(OMMDC)