An O(n^2) algorithm for the limited-capacity many-to-many point matching in one dimension

DOI10.1007/S00453-015-0044-4zbMATH Open1350.68276arXiv1210.8123OpenAlexW2163494942MaRDI QIDQ329283FDOQ329283

Authors: Fatemeh Rajabi-Alni, Alireza Bagheri 

Publication date: 21 October 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Given two point sets S and T, in a many-to-many matching between S and T each point in S is assigned to one or more points in T and vice versa. A generalization of the many-to-many matching problem is the limited capacity many-to-many matching problem, where the number of points that can be matched to each point, that is the capacity of each point, is limited. In this paper, we provide an O(n^2) time algorithm for the one dimensional minimum-cost limited capacity many-to-many matching problem, where |S| + |T| = n. Our algorithm improves the best previous time complexity of O(k(n^2)), that in which k is the largest capacity of the points in the union of S and T. In this problem, both S and T lie on the real line and the cost of matching s in S to t in T is equal to the distance between s and t.

Full work available at URL: https://arxiv.org/abs/1210.8123

Recommendations

• Efficient many-to-Many point matching in one dimension
• A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates
• Geometric algorithms for the minimum cost assignment problem
• Geometry Helps in Matching
• Bipartite graph matching for points on a line or a circle

zbMATH Keywords

limited-capacity point matchingmany-to-many point matchingone-dimensional point-matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Matching models (91B68)

Cites Work

• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An algorithm for computing the restriction s|caffold assignment problem in computational biology
• Two special cases of the assignment problem
• Distance measures for point sets and their computation
• Efficient many-to-Many point matching in one dimension
• Title not available (Why is that?)

Cited In (2)

• Comment: Matching methods for observational studies derived from large administrative databases
• Efficient many-to-Many point matching in one dimension

This page was built for publication: An \(O(n^2)\) algorithm for the limited-capacity many-to-many point matching in one dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329283)