A faster algorithm for the limited-capacity many-to-many point matching in one dimension

Autor:	Rajabi-Alni, Fatemeh, Bagheri, Alireza, Minaei-Bidgoli, Behrouz
Rok vydání:	2019
Předmět:	Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	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-> 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, where S and T are points lying on a line, and the cost of matching p in S to q in T equals the l_2 distance between p,q. Our algorithm improves the previous best-known quadratic time algorithm. Comment: 31 pages, 8 figures. arXiv admin note: text overlap with arXiv:1702.01083
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1904.03015 Zobrazit plný text záznamu View this record from Arxiv