BARC/MIAO talk by Allan Sapucaia

Tuesday, 22 March 2022, Allan Sapucaia, PhD at the University of Campinas, Brasil, will give a talk on "Solving Large Scale Instances of a Geometric Set Cover Problem with Coloring Conflicts".

Title: Solving Large Scale Instances of a Geometric Set Cover Problem with Coloring Conflicts

Abstract: When designing wireless networks, one wants to install antennas ensuring that all important regions are covered. There are many different secondary goals to consider such as minimizing the number of antennas, or ensuring that the network can still work even when some of the antennas are down.
In this talk, we will discuss a  geometric wireless network design problem where we want to minimize the number of antennas, while constrained by frequency assignment conflicts. We will study a Integer Linear Program model for this problem, and discuss how it can be improved using both  its geometric and graph-theoretical aspects. We show that the problem can be  efficiently solved in practice using decomposition and conclude by providing theoretical explanations for its performance.

Bio: Allan Sapucaia is a PhD Candidate in Combinatorial Optimization at the University of Campinas. His research employs Operation Research techniques to solve hard Computational Geometry problems in practice.