Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set
Abstract: Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric versions of these problems and present new online and dynamic algorithms for them. In the online version of set cover (resp. hitting set), m sets (resp. n points) are give n points (resp. m sets) arrive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution.
For online set cover for (axis-parallel) squares of arbitrary sizes, we present a tight O(log n)-competitive algorithm. In the same setting for hitting set, we provide a O(log N)-competitive algorithm, assuming that all points have integral coordinates in [0,N)^2. No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems).
For both dynamic set cover and hitting set with d-dimensional hyperrectangles, we obtain (logm)^(O(d))-approximation algorithms with (logm)^(O(d)) worst-case update time. This partially answers an open question posed by Chan et al. [SODA'22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an extended quad-tree approach and a frequency reduction technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.
This is a joint work with Aditya Lonkar, Rahul Saladi, Aditya Subramanian, and Andreas Wiese.
For online set cover for (axis-parallel) squares of arbitrary sizes, we present a tight O(log n)-competitive algorithm. In the same setting for hitting set, we provide a O(log N)-competitive algorithm, assuming that all points have integral coordinates in [0,N)^2. No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems).
For both dynamic set cover and hitting set with d-dimensional hyperrectangles, we obtain (logm)^(O(d))-approximation algorithms with (logm)^(O(d)) worst-case update time. This partially answers an open question posed by Chan et al. [SODA'22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an extended quad-tree approach and a frequency reduction technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.
This is a joint work with Aditya Lonkar, Rahul Saladi, Aditya Subramanian, and Andreas Wiese.
Speaker Bio
Arindam Khan is an Assistant Professor at the Department of Computer Science and Automation at the Indian Institution of Science Bengaluru. He did his Ph.D. from Georgia Institute of Technology, Atlanta, USA and undergraduate studies from IIT Kharagpur. He is broadly interested in the design and analysis of algorithms and theoretical computer science. His current research area includes Approximation Algorithms, Online Algorithms, Fairness, and Learning Theory.
He is a recipient of Prof. Priti Shankar Teaching Award, MFCS'20 Best paper award, Pratiksha Trust Young Investigator Award, and Google India Research Award.