|
Computer Science Seminar Date: Wednesday, 20 August 2025 Time: 2:00 PM Venue: Seminar Hall Online and Dynamic Algorithms for Geometric Set Cover Aditya Subramanian IISc, Bangalore. 20-08-25 Abstract Set Cover is one of the classical problems in theoretical computer science, which was among the original 21 problems shown to be NP-hard by Karp. For the general version of the problem, a simple greedy O(log n)-approximation is known, while it is also known that (under certain assumptions) a better approximation cannot be obtained. We study geometric variants of the problem where we are given m sets(which are geometric objects like squares or rectangles), and n points, and the goal is to pick the minimum number of sets so as to cover all the points. Many such geometric variants are also known to be NP-hard, but we study the problem under the paradigm of "algorithms under uncertainty" where the entire input is not known upfront, making the problem even harder. In this talk, we will first introduce some such paradigms, namely online algorithms, dynamic algorithms, streaming algorithms, etc. and then consider the set cover problem in these settings. Surprisingly, for online set cover on squares, we obtain a tight O(log n)-competitive algorithm, which matches the offline general set cover results. Further in the dynamic setting, for much more general shapes (hyperrectangles in d-dimensions) we show polylogarithmic approximations, in polylogarithmic update time. This is based on joint work with Arindam Khan, Aditya Lonkar, Saladi Rahul and Andreas Wiese, that appeared in SoCG'23.
|
