I, hereby, invite you on behalf of the School of Mathematical and Computational Sciences IACS, to attend a talk by Dr. Aniket Basu Roy, a post-doc researcher at Aarhus University.


Venue: CV Raman Hall

Date: August 10, 2023 (Thursday)

Time: 12:45 pm - 1:30 pm


Title: Effectiveness of Local Search for Geometric Packing and Covering Problems


Abstract: As Papadimitriou and Steiglitz aptly put it, "Local search is based on what is perhaps the oldest optimization method — trial and error." This presentation delves into a local search framework tailored for solving geometric optimization problems, which in turn delivers a polynomial time approximation scheme (PTAS). This PTAS was independently introduced in two seminal papers from 2009. The talk subsequently explores the efficacy of this framework in tackling the ensuing problems: 1) Packing of geometric objects with linear union complexity, 2)finding a maximum-sized diverse subset of curves from a given input set, and 3) covering the boundary of a simple orthogonal polygon with the fewest possible rectangles. Furthermore, the presentation encompasses the limitations inherent in this framework and outlines several open problems concerning the above-mentioned problems.


Thanks and regards,
Dr. Partha Basuchowdhuri
Assistant Professor
School of Mathematical and Computational Sciences
Indian Association for the Cultivation of Science