Fekete, Sándor P. ;
Kleist, Linda ;
Krupke, Dominik
Minimum Scan Cover with Angular Transition Costs
Abstract
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs (msc), we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan.
We show that msc is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in Θ(log χ(G)), while for 3D the minimum scan time is not upper bounded by χ(G). We use this relationship to prove that the existence of a constantfactor approximation implies P=NP, even for onedimensional instances. In 2D, we show that it is NPhard to approximate a minimum scan cover within less than a factor of 3/2, even for bipartite graphs; conversely, we present a 9/2approximation algorithm for this scenario. Generally, we give an O(c)approximation for kcolored graphs with k ≤ χ(G)^c. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
BibTeX  Entry
@InProceedings{fekete_et_al:LIPIcs:2020:12201,
author = {S{\'a}ndor P. Fekete and Linda Kleist and Dominik Krupke},
title = {{Minimum Scan Cover with Angular Transition Costs}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {43:143:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12201},
URN = {urn:nbn:de:0030drops122014},
doi = {10.4230/LIPIcs.SoCG.2020.43},
annote = {Keywords: Graph scanning, graph coloring, angular metric, complexity, approximation, scheduling}
}
08.06.2020
Keywords: 

Graph scanning, graph coloring, angular metric, complexity, approximation, scheduling 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 