Document Open Access Logo

Minimum Scan Cover with Angular Transition Costs

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.43.pdf
  • Filesize: 2.68 MB
  • 18 pages

Document Identifiers

Author Details

Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Germany
Linda Kleist
  • Department of Computer Science, TU Braunschweig, Germany
Dominik Krupke
  • Department of Computer Science, TU Braunschweig, Germany

Acknowledgements

We thank Phillip Keldenich, Irina Kostitsyna, Christian Rieck, and Arne Schmidt for helpful algorithmic discourse, Kenny Cheung (NASA) and Christian Schurig (European Space Agency) for joint work on intersatellite communication, and Karl-Heinz Glaßmeier for discussions of astrophysical aspects.

Cite AsGet BibTex

Sándor P. Fekete, Linda Kleist, and Dominik Krupke. Minimum Scan Cover with Angular Transition Costs. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.43

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 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Computational geometry
Keywords
  • Graph scanning
  • graph coloring
  • angular metric
  • complexity
  • approximation
  • scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. The angular-metric traveling salesman problem. SIAM J. Comp., 29(3):697-711, 1999. Google Scholar
  2. Ali Allahverdi. The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, 246(2):345-378, 2015. Google Scholar
  3. Ali Allahverdi, Jatinder N.D. Gupta, and Tariq Aldowaisan. A review of scheduling research involving setup considerations. Omega, 27(2):219-239, 1999. Google Scholar
  4. Ali Allahverdi, C.T. Ng, T.C. Edwin Cheng, and Mikhail Y. Kovalyov. A survey of scheduling problems with setup times or costs. European journal of operational research, 187(3):985-1032, 2008. Google Scholar
  5. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia. Optimal covering tours with turn costs. In Proc. 12th ACM-SIAM Symp. Disc. Alg. (SODA), pages 138-147, 2001. Google Scholar
  6. Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia. Optimal covering tours with turn costs. SIAM J. Comp., 35(3):531-566, 2005. Google Scholar
  7. Rom Aschner and Matthew J. Katz. Bounded-angle spanning tree: modeling networks with angular constraints. Algorithmica, 77(2):349-373, 2017. Google Scholar
  8. Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen. Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost. In Proc. 33rd Symp. Comp. Geom. (SoCG), pages 62:1-62:5, 2017. Google Scholar
  9. Paz Carmi, Matthew J. Katz, Zvi Lotker, and Adi Rosén. Connectivity guarantees for wireless networks with directional antennas. Computational Geometry, 44(9):477-485, 2011. Google Scholar
  10. Julia Chuzhoy and Sanjeev Khanna. Hardness of cut problems in directed graphs. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC '06, pages 527-536, New York, NY, USA, 2006. ACM. Google Scholar
  11. Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O'Rourke. The Open Problems Project. URL: http://cs.smith.edu/~orourke/TOPP/.
  12. Sándor P. Fekete and Dominik Krupke. Covering tours and cycle covers with turn costs: Hardness and approximation. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC), pages 224-236, 2019. Google Scholar
  13. Sándor P. Fekete and Dominik Krupke. Practical methods for computing large covering tours and cycle covers with turn cost. In Proc. 21st SIAM Workshop Alg. Engin. Exp. (ALENEX), pages 186-198, 2019. Google Scholar
  14. Sándor P. Fekete and Gerhard J. Woeginger. Angle-restricted tours in the plane. Comp. Geom., 8:195-218, 1997. Google Scholar
  15. Sándor P. Fekete, Linda Kleist, and Dominik Krupke. Minimum scan cover with angular transition costs, 2020. URL: http://arxiv.org/abs/2003.08816.
  16. Mike Fellows, Panos Giannopoulos, Christian Knauer, Christophe Paul, Frances A. Rosamond, Sue Whitesides, and Nathan Yu. Milling a graph with turn costs: A parameterized complexity perspective. In Proc 36th Worksh. Graph Theo. Conc. Comp. Sci. (WG), pages 123-134, 2010. Google Scholar
  17. Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7(1):465, June 1992. Google Scholar
  18. Edna Ayako Hoshino. The minimum cut cover problem. Electronic Notes in Discrete Mathematics, 37:255-260, 2011. URL: https://doi.org/10.1016/j.endm.2011.05.044.
  19. Subhash Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 600-609. IEEE, 2001. Google Scholar
  20. Haje Korth, Michelle F. Thomsen, Karl-Heinz Glassmeier, and W. Scott Phillips. Particle tomography of the inner magnetosphere. Journal of Geophysical Research: Space Physics, 107(A9):SMP-5, 2002. Google Scholar
  21. Dominik Krupke, Volker Schaus, Andreas Haas, Michael Perk, Jonas Dippel, Benjamin Grzesik, Mohamed Khalil Ben Larbi, Enrico Stoll, Tom Haylock, Harald Konstanski, Kattia Flores Pozzo, Mirue Choi, Christian Schurig, and Sándor P. Fekete. Automated data retrieval from large-scale distributed satellite systems. In 2019 IEEE 15th International Conference on Automation Science and Engineering (CASE), pages 1789-1795. IEEE, 2019. Google Scholar
  22. Richard Loulou. Minimal cut cover of a graph with an application to the testing of electronic boards. Oper. Res. Lett., 12(5):301-305, November 1992. Google Scholar
  23. Rajeev Motwani and Joseph (Seffi) Naor. On exact and approximate cut covers of graphs. Technical report, Stanford University, Stanford, CA, USA, 1994. Google Scholar
  24. Herbert Robbins. A remark on stirling’s formula. The American Mathematical Monthly, 62(1):26-29, 1955. Google Scholar
  25. Yuri N. Sotskov, Alexandre Dolgui, and Frank Werner. Mixed graph coloring for unit-time job-shop scheduling. International Journal of Mathematical Algorithms, 2(4):289-323, 2001. Google Scholar
  26. Kaoru Watanabe, Masakazu Sengoku, Hiroshi Tamura, and Shoji Shinoda. Cut cover problem in directed graphs. In IEEE. APCCAS 1998. 1998 IEEE Asia-Pacific Conference on Circuits and Systems. Microelectronics and Integrating Systems. Proceedings (Cat. No.98EX242), pages 703-706, 1998. Google Scholar
  27. Rico Zenklusen. A 1.5-approximation for path tsp. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 1539-1549, Philadelphia, PA, USA, 2019. Society for Industrial and Applied Mathematics. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact