论文标题
最小扫描覆盖范围有角度过渡成本
Minimum Scan Cover with Angular Transition Costs
论文作者
论文摘要
我们提供了一项全面研究，该研究是在卫星通信和天体物理学背景下由问题促使的自然几何优化问题。在问题最小扫描覆盖范围（MSC）中，我们给了我们一个嵌入欧几里得空间中的图形$ g $。 $ g $的边缘需要扫描，即从两个顶点探测。为了扫描它们的边缘，两个顶点需要彼此面对；更改顶点的标题需要与相应的转弯角成比例的时间。我们的目标是最大程度地减少所有扫描完成的时间，即计算最低制造商的时间表。 我们表明，MSC与图形着色和最小（有向和无方向性）的切割盖问题密切相关。特别是，我们表明1D和2D实例的最小扫描时间在于$θ（\ logC（g））$，而对于3D，最小扫描时间不受$χ（g）$的上限。我们使用这种关系来证明恒定因子近似的存在意味着$ p = np $，即使对于一维实例。在2D中，我们表明，即使在两部分图形中，也要在$ \ frac {3} {2} $的范围内近似最小扫描盖是NP-HARD；相反，我们提出了此情况的$ \ frac {9} {2} $ - 近似算法。通常，我们给出$ o（c）$ - $ k $彩色的图形，并带有$ k \ leqχ（g）^c $。对于一般度量成本函数，我们提供近似算法，其性能保证取决于图形的树木。
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 $\frac{3}{2}$, even for bipartite graphs; conversely, we present a $\frac{9}{2}$-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $k\leq χ(G)^c$. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
