Research Projects

In this project, I considered a few optimization problems that have real-life applications and the goal is to design (approximation) algorithms for geometric optimization problems. The project is mostly focused on designing efficient approximation algorithms and polynomial-time approximation schemes (PTASs) for variant geometric optimization problems such as facility location problem and its variants, covering and packing problems, etc. These problems have geometry inherently and include covering (or packing) one type of geometric object(s) (for example, points, disks, rectangles, line segments, etc.) with a minimum (or maximum) number of some other type of geometric object(s). The aforesaid problems are of broad and current interest due to its wide range of real-life applications in VLSI, city planning, clustering, network construction, etc. This motivated me to work on these problems. For many geometric optimization problems, it is next to impossible to design algorithms that run in polynomial-time to compute optimal solutions, unless P = NP. For such problems, I love to design computationally efficient approximation algorithms and prove the solution returned by my algorithms is not far from optimal solutions. Here, the challenge is to establish a relation between the values of the optimal solution and the solution returned by approximation algorithms without even knowing what an optimal solution is. I outlined some interesting problems below that I would like to work on. To the best of my knowledge, the proposed problems are open problems even till today. Problems in Imprecise Setup: It may not always be possible to have the precise or exact co-ordinates (or locations) due to several reasons like signal obstruction, multi-path effect, etc. In such cases, the classical geometric algorithms might fail to produce correct solutions with imprecise data. Generally, the input instances are provided as regions (also known as regions of uncertainty) such as a set of points, disks, rectangles, line segments, etc. The objective is to choose a point from each region such that the cost function of some desired geometric structure (e.g., a minimum spanning tree, a convex hull, a traveling salesman tour, an enclosing circle, etc.) or a measure (e.g., diameter, pairwise distance, shortest path, bounding box, etc.) constructed on the chosen point set is as minimum or maximum as possible.