Minimum scan cover with angular transition costs

DOI10.1137/20M1368161MaRDI QIDQ4997133zbMATH OpenOpenAlexFDO

Authors Sándor P. Fekete, Linda Kleist, Dominik Krupke

Publication date 28 June 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.08816

zbMATH Keywords

angular metricapproximationgraph coloringgraph scanningscheduling

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Applications of graph theory (05C90) Metric geometry (51F99) Combinatorial complexity of geometric structures (52C45) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

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 $Theta(logchi(G))$, while for 3D the minimum scan time is not upper bounded by $chi(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 $frac32$, even for bipartite graphs; conversely, we present a $frac92$-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $kleqchi(G{)}^c$. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.

Recommendations

• Minimum covering with travel cost
• Minimum covering with travel cost
• Algorithms - ESA 2003
• The minimum generalized vertex cover problem
• On the multi-radius cover problem

Cites work

• A 1.5-approximation for path TSP
• A Remark on Stirling's Formula
• A survey of scheduling problems with setup times or costs
• An improved approximation algorithm for TSP in the half integral case
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Angle-restricted tours in the plane.
• Bounded-angle spanning tree: modeling networks with angular constraints
• Connectivity guarantees for wireless networks with directional antennas
• Covering tours and cycle covers with turn costs: hardness and approximation
• Forests, frames, and games: Algorithms for matroid sums and applications
• Hardness of cut problems in directed graphs
• scientific article; zbMATH DE number 1731177 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Milling a graph with turn costs: a parameterized complexity perspective
• Minimal cut cover of a graph with an application to the testing of electronic boards
• Optimal covering tours with turn costs
• Optimal Covering Tours with Turn Costs
• Practical methods for computing large covering tours and cycle covers with turn cost
• The Angular-Metric Traveling Salesman Problem
• The minimum cut cover problem
• The third comprehensive survey on scheduling problems with setup times/costs

Cited in

(4)

• scientific article; zbMATH DE number 7760172 (Why is no real title available?)
• Edge sparsification for geometric tour problems
• Minimum Scan Cover and Variants: Theory and Experiments
• Minimum scan cover and variants -- theory and experiments

This page was built for publication: Minimum scan cover with angular transition costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997133)