Home Bookmarks Papers Blog

Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs

$\newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$
Sariel Har-Peled, and Everett Yang.
We present a $(1- \eps)$-approximation algorithms for maximum cardinality matchings in disk intersection graphs -- all with near linear running time. We also present an estimation algorithm that returns $(1\pm \eps)$-approximation to the size of such matchings -- this algorithm runs in linear time for unit disks, and $O(n \log n)$ for general disks (as long as the density is relatively small).
PDF. : arXiv.
Last modified: Sat 2022-07-23 19:55:48 UTC 2022 by Sariel Har-Peled