| Naslov: | Geometric matching and bottleneck problems |
|---|
| Avtorji: | ID Cabello, Sergio (Avtor)
ID Cheng, Siu-Wing (Avtor)
ID Cheong, Otfried (Avtor)
ID Knauer, Christian (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (959,05 KB)
MD5: BD886FA6FD5797E936ECDFECA6F0A6A0
 URL - Izvorni URL, za dostop obiščite https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.31
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.08 - Objavljeni znanstveni prispevek na konferenci |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | Let $P$ be a set of at most $n$ points and let $R$ be a set of at most $n$ geometric ranges, such as disks or rectangles, where each $p \in P$ has an associated supply $s_{p} > 0$, and each $r \in R$ has an associated demand $d_{r} > 0$. A (many-to-many) matching is a set ${\mathcal A}$ of ordered triples $(p,r,a_{pr}) \in P \times R \times {\mathbb R}_{>0}$ such that $p \in r$ and the $a_{pr}$'s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing $\sum_{(p,r,a_{pr}) \in {\mathcal A}} a_{pr}$. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of $n$ red points $P$ and a set of $n$ blue points $Q$ that minimizes the length of the longest edge. For the $L_\infty$-metric, we can do this in time $O(n^{1+\varepsilon})$ in any fixed dimension, for the $L_2$-metric in the plane in time $O(n^{4/3 + \varepsilon})$, for any $\varepsilon > 0$. |
|---|
| Ključne besede: | many-to-many matching, bipartite, planar, geometric matching, approximation |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Leto izida: | 2024 |
|---|
| Št. strani: | Str. 31:1-31:15 |
|---|
| PID: | 20.500.12556/DiRROS-20967  |
|---|
| UDK: | 004.42 |
|---|
| DOI: | 10.4230/LIPIcs.SoCG.2024.31 |
|---|
| COBISS.SI-ID: | 218353667 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 11.12.2024 |
|---|
| Število ogledov: | 54 |
|---|
| Število prenosov: | 22 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
