Geometry Seminar

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems

Speaker: Sujoy Bhore, IIT Bombay

Location: Online Zoom-only

Videoconference link: https://youtu.be/_x71mzd0eOo

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+\varepsilon)\)-approximation algorithm for MVC with \(O(\mathop{\mathrm{polylog}} n)\) amortized update time. Furthermore, for disks in the plane or hypercubes in any constant dimension, we give the first fully dynamic \((1+\varepsilon)\)- approximation algorithm for MVC with \(O(\mathop{\mathrm{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+\varepsilon)\)-approximation algorithm for MCM with \(O(\mathop{\mathrm{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.