一维需求点集的高效多对多匹配 (Efficient Many-To-Many Matching of Points with Demands in One Dimension)

Given two point sets $S$ and $T$, the minimum-cost many-to-many matching with demands (MMD) problem is the problem of finding a minimum-cost many-to-many matching between $S$ and $T$ such that each point of $S$ (respectively $T$) is matched to at least a given number of the points of $T$ (respectively $S$). We propose the first $O\left(n^2\right)$-time algorithm for computing a one dimensional MMD (OMMD) of minimum cost between $S$ and $T$, where $\left|S\right|+\left|T\right|=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 equals the Euclidean 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 the first $O(n^2)$-time algorithm for the minimum-cost one dimensional MMDC (OMMDC) problem.

翻译：给定两个点集$S$和$T$，带需求的最小代价多对多匹配（MMD）问题旨在寻找$S$与$T$之间代价最小的多对多匹配，使得$S$（对应地$T$）中的每个点至少匹配到$T$（对应地$S$）中给定数量的点。针对$S$与$T$位于实数轴且匹配代价等于两点间欧氏距离的一维MMD（OMMD）问题，我们提出了首个计算最小代价OMMD的$O\\left(n^2\\right)$时间算法，其中$\\left|S\\right|+\\left|T\\right|=n$。此外，我们研究了MMD问题的广义形式——带需求与容量的多对多匹配（MMDC）问题，其中每个点除需求外还具有容量限制。针对一维MMDC（OMMDC）问题，我们给出了首个求解最小代价OMMDC的$O(n^2)$时间算法。