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

arXiv: https://arxiv.org/abs/1904.03015 · HTML: https://mlsanity.com/paper/1904.03015/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2019.

## Built on by (most cited first, 1 of 1)

- [Many-to-Many Matching via Sparsity Controlled Optimal Transport](https://mlsanity.com/paper/2503.24204/) (2025)

## Abstract (arXiv)

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:Scup 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 l2 distance between p,q. Our algorithm improves the previous best-known quadratic time algorithm.