Minimum Scan Cover

Exploring the Combinatorial Complexities of Synchronizing Directional Antennas' Rotations. The strongest parts of this project are the theoretical results, which are published in the SIAM Journal of Discrete Mathematics

Minimum Scan Cover - A visualization of a step in the approximation algorithm.

In this project, we conducted an in-depth study of a graph optimization problem related to transition costs in adjacent edges, a scenario commonly encountered in intersatellite communication with directed antennas. The investigation covered both theoretical and practical aspects. Theoretically, we analyzed the complexity and approximation strategies for various objectives, emphasizing graphs embedded in the plane. One of our key theoretical findings was the strong correlation between minimizing makespan and the chromatic number of the graph. Additionally, we provided an improved upper bound of ⌈log2 𝜒(𝐺) + 1/2 · log2 log2 𝜒(𝐺) + 1⌉ for the minimum directed cut cover number, which is essentially tight in general.

On the practical side, we assessed the computational complexity of solving this problem. Our findings indicated that while mixed integer programming approaches were inadequate, a SAT-based constraint programming method proved effective for solving medium-sized instances optimally. Additionally, the project involved a thorough evaluation of the solution quality produced by various approximation algorithms and heuristics, providing insights into their effectiveness in practical applications.

  • Chapter 2+3 of my dissertation contains an extended version of all the results below and more.
  • Minimum Scan Cover and Variants: Theory and Experiments Kevin Buchin , Alexander Hill , Sándor Fekete , Linda Kleist , Irina Kostitsyna , and Dominik Krupke, Roel Lambers, Martijn Struijs ACM Journal of Experimental Algorithmics, Jan 2022
  • Minimum Scan Cover with Angular Transition Costs Sándor P. Fekete , Linda Kleist , and Dominik Krupke SIAM J. Discret. Math., Jan 2021
  • Minimum Scan Cover and Variants - Theory and Experiments Kevin Buchin , Sándor P. Fekete , Alexander Hill , Linda Kleist , Irina Kostitsyna , and Dominik Krupke, Roel Lambers, Martijn Struijs In 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France , Jan 2021
  • Minimum Scan Cover with Angular Transition Costs Sándor P. Fekete , Linda Kleist , and Dominik Krupke In 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland , Sep 2020