Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929442503262208 |
|---|---|
| author | Bhore, Sujoy Chan, Timothy M. |
| author_facet | Bhore, Sujoy Chan, Timothy M. |
| contents | We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum independent set (MIS), minimum vertex cover (MVC), and maximum-cardinality matching (MCM). Highlights of our results include the following:
* For $n$ axis-aligned boxes in any constant dimension $d$, we give an $O(\log \log n)$-approximation algorithm for MPS that runs in $O(n^{1+δ})$ time for an arbitrarily small constant $δ>0$. This significantly improves the previous $O(\log\log n)$-approximation algorithm by Agarwal, Har-Peled, Raychaudhury, and Sintos (SODA~2024), which ran in $O(n^{d/2}\mathop{\rm polylog} n)$ time.
* Furthermore, we show that our algorithm can be made fully dynamic with $O(n^δ)$ amortized update time. Previously, Agarwal et al.~(SODA~2024) obtained dynamic results only in $\mathbb{R}^2$ and achieved only $O(\sqrt{n}\mathop{\rm polylog} n)$ amortized expected update time.
* For $n$ axis-aligned rectangles in $\mathbb{R}^2$, we give an $O(1)$-approximation algorithm for MIS that runs in $O(n^{1+δ})$ time. Our result significantly improves the running time of the celebrated algorithm by Mitchell (FOCS~2021) (which was about $O(n^{21})$), and answers one of his open questions. Our algorithm can also be made fully dynamic with $O(n^δ)$ amortized update time.
* For $n$ (unweighted or weighted) fat objects in any constant dimension, we give a dynamic $O(1)$-approximation algorithm for MIS with $O(n^δ)$ amortized update time.
* For disks in $\mathbb{R}^2$ or hypercubes in any constant dimension, we give the first fully dynamic $(1+\varepsilon)$-approximation algorithms for MVC and MCM with $O(\mathop{\rm polylog}n)$ amortized update time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_20659 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching Bhore, Sujoy Chan, Timothy M. Computational Geometry Data Structures and Algorithms We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum independent set (MIS), minimum vertex cover (MVC), and maximum-cardinality matching (MCM). Highlights of our results include the following: * For $n$ axis-aligned boxes in any constant dimension $d$, we give an $O(\log \log n)$-approximation algorithm for MPS that runs in $O(n^{1+δ})$ time for an arbitrarily small constant $δ>0$. This significantly improves the previous $O(\log\log n)$-approximation algorithm by Agarwal, Har-Peled, Raychaudhury, and Sintos (SODA~2024), which ran in $O(n^{d/2}\mathop{\rm polylog} n)$ time. * Furthermore, we show that our algorithm can be made fully dynamic with $O(n^δ)$ amortized update time. Previously, Agarwal et al.~(SODA~2024) obtained dynamic results only in $\mathbb{R}^2$ and achieved only $O(\sqrt{n}\mathop{\rm polylog} n)$ amortized expected update time. * For $n$ axis-aligned rectangles in $\mathbb{R}^2$, we give an $O(1)$-approximation algorithm for MIS that runs in $O(n^{1+δ})$ time. Our result significantly improves the running time of the celebrated algorithm by Mitchell (FOCS~2021) (which was about $O(n^{21})$), and answers one of his open questions. Our algorithm can also be made fully dynamic with $O(n^δ)$ amortized update time. * For $n$ (unweighted or weighted) fat objects in any constant dimension, we give a dynamic $O(1)$-approximation algorithm for MIS with $O(n^δ)$ amortized update time. * For disks in $\mathbb{R}^2$ or hypercubes in any constant dimension, we give the first fully dynamic $(1+\varepsilon)$-approximation algorithms for MVC and MCM with $O(\mathop{\rm polylog}n)$ amortized update time. |
| title | Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.20659 |