Dear colleagues,

 

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