文章基本信息

标题：Minimum Scan Cover with Angular Transition Costs
本地全文：下载
作者：S{'a}ndor P. Fekete ; Linda Kleist ; Dominik Krupke 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：43:1-43:18
DOI：10.4230/LIPIcs.SoCG.2020.43
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 constant-factor approximation implies P=NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of 3/2, even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an O(c)-approximation for k-colored graphs with k â¤ Ï(G)^c. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
关键词：Graph scanning; graph coloring; angular metric; complexity; approximation; scheduling