[Proof Complexity] [SPAM] Seminar tomorrow Tue Mar 22 at 14:00 CET with Allan Sapucaia: Solving large scale instances of a geometric set cover problem with coloring conflicts

Jakob Nordström jn at di.ku.dk
Mon Mar 21 11:18:44 CET 2022

Dear all,

After a long winter break, the MIAO seminars are finally set to resume, and on very short notice at that!

It is my pleasure to invite you to a seminar tomorrow Tuesday March 22 at 14:00 CET with Allan Sapucaia from University of Campinas. The title of the talk is "Solving large scale instances of a geometric set cover problem with coloring conflicts" and you find the abstract at the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. Local participants are welcome to seminar room A107 in the Hans Christian Ørsted Building. Other participants are welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming video seminars can be found at http://www.jakobnordstrom.se/videoseminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström


Tuesday March 22 at 14:15 in seminar room A107, Hans Christian Ørsted Building, Universitetsparken 5, University of Copenhagen, and on Zoom
Solving large scale instances of a geometric set cover problem with coloring conflicts
(Allan Sapucaia, University of Campinas)

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.

Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98

More information about the Proof-Complexity mailing list