Dena Tayebi

Geometric set cover problems are fundamental optimization problems in the area of combinatorial geometry, with numerous applications such as facility location and clustering. In these problems, a set of points and regions are given, each region covering some point and the objective is to find the minimum set of regions that cover all the points. Since the geometric set cover problems are typically NP-hard, researchers have used a large number of approximation algorithms and meta-heuristics to solve these problems, such as genetic algorithms, tabu search, ant colony optimization, etc. While approximation algorithms require careful design and analysis (and very few good solutions are known), the meta-heuristics require careful configuration of parameters and often lead to solutions that are far from optimal. As part of my Ph.D., I would like to explore if machine learning can be leveraged to solve the geometric set cover problems exactly. The key idea is to train a supervised learning model that predicts which regions are part of the final solution and which are not, based on training on smaller instances (for which exact computation is feasible). The nodes/edges, for which the classification model is confident are not part of the final solution, can be pruned away. This pruning will help to scale-up the exact algorithms for solving the geometric set-cover problems.
We will then examine variants of geometric set-cover problems such as the famous k-means clustering, k-center, k-medoid etc and apply the same framework there. Efficient exact solutions to these problems will have a significant impact in the areas of machine learning and optimization algorithms. With these examples, we want to demonstrate that supervised learning is viable for solving large structured instances of NP-hard problems.