Geometric matching and bottleneck problems

Cabello, Sergio (avtor), Cheng, Siu-Wing (avtor), Cheong, Otfried (avtor), Knauer, Christian (avtor)

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$.

• Jezik: Angleški jezik
• Ključne besede: many-to-many matching, bipartite, planar, geometric matching, approximation
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2024
• Št. strani: Str. 31:1-31:15
• PID: 20.500.12556/RUL-165635
• UDK: 004.42
• DOI: 10.4230/LIPIcs.SoCG.2024.31
• COBISS.SI-ID: 218353667
• Datum objave v RUL: 11.12.2024

Gradivo je del monografije

• Naslov: 40th International Symposium on Computational Geometry : SoCG 2024, June 11-14, 2024, Athens, Greece
• Uredniki: Wolfgang Mulzer, Jeff M. Phillips
• Kraj izida: Saarbrücken/Wadern
• Založnik: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Leto izida: 2024
• ISBN: 978-3-95977-316-4
• COBISS.SI-ID: 218546691
• Naslov zbirke: Leibniz international proceedings in informatics
• Številčenje v zbirki: ǂvol. ǂ293
• ISSN zbirke: 1868-8969

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.