Geometry Seminar

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems

Speaker: Sujoy Bhore, IIT Bombay

Location: Online Zoom-only

Date: Tuesday, January 28, 2025, 2 p.m.

Synopsis:

We developed 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+\delta})$ time for an arbitrarily small constant $\delta > 0$, which can be made fully dynamic with $O(n^\delta)$ amortized update time.
For axis-aligned rectangles, we give an $O(1)$-approximation algorithm for MIS that runs in $O(n^{1+\delta)$ time, which can be made fully dynamic with $O(n^\delta)$ amortized update time. For (unweighted or weighted) fat objects in any constant dimension, we give a dynamic $O(1)$-approximation algorithm for MIS with $O(n^\delta)$ amortized update time.
For $n$ axis-aligned rectangles, we give a dynamic $(3/2+\eps)$-approximation algorithm for MVC with $O(polylog n)$ amortized update time. Furthermore, for disks in the plane or hypercubes in any constant dimension, we give the first fully dynamic $(1+\eps)$- approximation algorithm for MVC with $O(polylog n)$ amortized update time.
For (monochromatic or bichromatic) disks in the plane or hypercubes in any constant dimension, we give the first fully dynamic $(1+\eps)$-approximation algorithm for MCM with $O(polylog n)$ amortized update time.

This joint work with Timothy M. Chan (UIUC) appeared in SODA 2025.

Notes:

Contact Boris Aronov to be placed on the mailing list with notifications and Zoom seminar info.