Matching elements from two sets (bipartite matching), a fundamental subject in computer science, is used in applications such as bipartite data matching (e.g. graph edit distance computation and semantic data matching) and allocating resources in a wireless network. Given two sets S and T, a limited-capacity many-to-many matching (LCMM) between S and T matches each element p in S (resp. T) to at least 1 and at most Cap(p) elements in T (resp. S), where the function <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7408_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="157" /> </InlineMediaObject> <EquationSource Format="TEX">$Cap:S\cup T\rightarrow \mathbb {Z}>0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>C</mi> <mi>a</mi> <mi>p</mi> <mo>:</mo> <mi>S</mi> <mo>∪</mo> <mi>T</mi> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">Z</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> denotes the capacity of p. In this paper, we present the first linear time algorithm for finding a minimum-cost one-dimensional LCMM (OLCMM) between S and T when S and T are points lying on a line; the cost of matching each point <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7408_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$p\in S$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>∈</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7408_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">$q\in T$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>∈</mo> <mi>T</mi> </mrow> </math></EquationSource> </InlineEquation> equals the Euclidean distance between p, q. Our dynamic programming algorithm improves the previous best-known quadratic time algorithm, and moreover, can be used with online arriving input points (which are not known in advance and arrive sequentially one by one).

An efficient algorithm for the limited-capacity many-to-many point matching in one dimension

期刊论文
发表日期：

2025年5月29日

查看全文

Fatemeh Rajabi-Alni,
Behrouz Minaei-Bidgoli,
Alireza Bagheri

摘要

Matching elements from two sets (bipartite matching), a fundamental subject in computer science, is used in applications such as bipartite data matching (e.g. graph edit distance computation and semantic data matching) and allocating resources in a wireless network. Given two sets S and T, a limited-capacity many-to-many matching (LCMM) between S and T matches each element p in S (resp. T) to at least 1 and at most Cap(p) elements in T (resp. S), where the function $Cap:S\cup T\rightarrow \mathbb {Z}>0$ $C a p : S \cup T \to Z > 0$ denotes the capacity of p. In this paper, we present the first linear time algorithm for finding a minimum-cost one-dimensional LCMM (OLCMM) between S and T when S and T are points lying on a line; the cost of matching each point $p\in S$ $p \in S$ to $q\in T$ $q \in T$ equals the Euclidean distance between p, q. Our dynamic programming algorithm improves the previous best-known quadratic time algorithm, and moreover, can be used with online arriving input points (which are not known in advance and arrive sequentially one by one).