{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:15Z","timestamp":1787323155020,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. 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. A real-world motivation arises in the context of satellite communication and astrophysics. 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(\\log \\chi (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 $\\nicefrac{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\\leq \\chi(G)^{c}$. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph.<\/jats:p>","DOI":"10.1137\/20m1368161","type":"journal-article","created":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T13:38:16Z","timestamp":1623937096000},"page":"1337-1355","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Scan Cover with Angular Transition Costs"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":true,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dominik","family":"Krupke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796312721"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.04.004"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0483(98)00042-5"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.06.060"},{"key":"atypb5","unstructured":"E. M. Arkin, M. A. Bender, E. D. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia,\n                      Optimal covering tours with turn costs\n                      , in Proc. of the Symposium on Discrete Algorithms (SODA), 2001, pp. 138-147."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434267"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0076-9"},{"key":"atypb8","first-page":"299","author":"Beardwood J.","year":"1959","journal-title":"Cambridge"},{"key":"atypb9","unstructured":"A. T. Becker, M. Debboun, S. P. Fekete, D. Krupke, and A. Nguyen,\n                      Zapping zika with a mosquito-managing drone: Computing optimal flight patterns with minimum turn cost\n                      , in Proc. of Symposium on Computational Geometry (SoCG), 2017, pp. 62:1-62:5."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.05.003"},{"key":"atypb11","first-page":"527","author":"Chuzhoy J.","year":"2006","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. P. Fekete and D. Krupke,\n                      Covering tours and cycle covers with turn costs: Hardness and approximation\n                      , in Proc. of Conference on Algorithms and Complexity (CIAC), 2019, pp. 224-236.","DOI":"10.1007\/978-3-030-17402-6_19"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"S. P. Fekete and D. Krupke,\n                      Practical methods for computing large covering tours and cycle covers with turn cost\n                      , in Proc. of SIAM Workshop on Algorithm Engineering and Experiments (ALENEX), 2019, pp. 186-198.","DOI":"10.1137\/1.9781611975499.15"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00012-0"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"M. Fellows, P. Giannopoulos, C. Knauer, C. Paul, F. A. Rosamond, S. Whitesides, and N. Yu,\n                      Milling a graph with turn costs: A parameterized complexity perspective\n                      , in Proc. of Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2010, pp. 123-134.","DOI":"10.1007\/978-3-642-16926-7_13"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758774"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90016-I"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2011.05.044"},{"key":"atypb20","unstructured":"A. R. Karlin, N. Klein, and S. O. Gharan,\n                      A (Slightly) Improved Approximation Algorithm for Metric TSP\n                      ,https:\/\/arxiv.org\/abs\/2007.01409, 2020."},{"key":"atypb21","first-page":"600","author":"Khot S.","year":"2001","journal-title":"IEEE"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1029\/2001JA000147"},{"key":"atypb23","first-page":"1789","author":"Krupke D.","year":"2019","journal-title":"New York"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90089-L"},{"key":"atypb25","unstructured":"R. Motwani and J. S. Naor,\n                      On Exact and Approximate Cut Covers of Graphs\n                      , Technical report, Stanford University, Stanford, CA, 1994."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.2307\/2308012"},{"key":"atypb27","first-page":"289","volume":"2","author":"Sotskov Y. N.","year":"2001","journal-title":"Int. J. Math. Algorithms"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"K. Watanabe, M. Sengoku, H. Tamura, and S. Shinoda,\n                      Cut cover problem in directed graphs\n                      , in Proc. of Asia-Pacific Conference on Circuits and Systems. Microelectronics and Integrating Systems (cat. no. 98EX242), 1998, pp. 703-706.","DOI":"10.1109\/APCCAS.1998.743918"},{"key":"atypb29","first-page":"1539","author":"Zenklusen R.","year":"2019","journal-title":"Philadelphia"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1368161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:52Z","timestamp":1787319892000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1368161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1368161"],"URL":"https:\/\/doi.org\/10.1137\/20m1368161","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}