Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/1904.05184 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915577531990016 |
|---|---|
| author | Rajabi-Alni, Fatemeh Minaei-Bidgoli, Behrouz |
| author_facet | Rajabi-Alni, Fatemeh Minaei-Bidgoli, Behrouz |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1904_05184 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Efficient Many-To-Many Matching of Points with Demands in One Dimension Rajabi-Alni, Fatemeh Minaei-Bidgoli, Behrouz Computational Geometry 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. |
| title | Efficient Many-To-Many Matching of Points with Demands in One Dimension |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/1904.05184 |