Document Open Access Logo

Minimum Scan Cover and Variants - Theory and Experiments

Authors Kevin Buchin , Sándor P. Fekete , Alexander Hill , Linda Kleist , Irina Kostitsyna , Dominik Krupke , Roel Lambers , Martijn Struijs

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.4.pdf
  • Filesize: 4.76 MB
  • 16 pages

Document Identifiers

Author Details

Kevin Buchin
  • Department of Mathematics & Computer Science, TU Eindhoven, The Netherlands
Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Germany
Alexander Hill
  • Department of Computer Science, TU Braunschweig, Germany
Linda Kleist
  • Department of Computer Science, TU Braunschweig, Germany
Irina Kostitsyna
  • Department of Mathematics & Computer Science, TU Eindhoven, The Netherlands
Dominik Krupke
  • Department of Computer Science, TU Braunschweig, Germany
Roel Lambers
  • Department of Mathematics & Computer Science, TU Eindhoven, The Netherlands
Martijn Struijs
  • Department of Mathematics & Computer Science, TU Eindhoven, The Netherlands

Funding

Work at TU Braunschweig was partially supported under grant FE407/21-1, "Computational Geometry: Solving Hard Optimization Problems" (CG:SHOP).

Cite As Get BibTex

Kevin Buchin, Sándor P. Fekete, Alexander Hill, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers, and Martijn Struijs. Minimum Scan Cover and Variants - Theory and Experiments. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.4

Abstract

We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs, 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 incurs some cost in terms of energy or rotation time that is proportional to the corresponding rotation angle. Our goal is to compute schedules that minimize the following objective functions: (i) in Minimum Makespan Scan Cover (MSC-MS), this is the time until all edges are scanned; (ii) in Minimum Total Energy Scan Cover (MSC-TE), the sum of all rotation angles; (iii) in Minimum Bottleneck Energy Scan Cover (MSC-BE), the maximum total rotation angle at one vertex.
Previous theoretical work on MSC-MS revealed a close connection to graph coloring and the cut cover problem, leading to hardness and approximability results. In this paper, we present polynomial-time algorithms for 1D instances of MSC-TE and MSC-BE, but NP-hardness proofs for bipartite 2D instances. For bipartite graphs in 2D, we also give 2-approximation algorithms for both MSC-TE and MSC-BE. Most importantly, we provide a comprehensive study of practical methods for all three problems. We compare three different mixed-integer programming and two constraint programming approaches, and show how to compute provably optimal solutions for geometric instances with up to 300 edges. Additionally, we compare the performance of different meta-heuristics for even larger instances.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Computational geometry
  • Applied computing → Operations research
Keywords
  • Graph scanning
  • angular metric
  • makespan
  • energy
  • bottleneck
  • complexity
  • approximation
  • algorithm engineering
  • mixed-integer programming
  • constraint programming

Metrics

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

Related Versions

Supplementary Materials

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. Eur. J. Oper. Res., 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. Eur. J. Oper. Res., 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 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. Sean Augenstein, Alejandra Estanislao, Emmanuel Guere, and Sean Blaes. Optimal scheduling of a constellation of Earth-imaging satellites, for maximal data throughput and efficient human management. In Int. Conf. Automated Planning & Scheduling, pages 345-352, 2016. Google Scholar
  9. 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 Symp. Comp. Geom. (SoCG), pages 62:1-62:5, 2017. Google Scholar
  10. Daniel Brélaz. New methods to color the vertices of a graph. Comm. ACM, 22(4):251-256, 1979. Google Scholar
  11. Kevin Buchin, Sándor P. Fekete, Alexander Hill, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers, and Martijn Struijs. Minimum scan cover and variants - theory and experiments, 2021. URL: http://arxiv.org/abs/2103.14599.
  12. Paz Carmi, Matthew J. Katz, Zvi Lotker, and Adi Rosén. Connectivity guarantees for wireless networks with directional antennas. Comp. Geom., 44(9):477-485, 2011. Google Scholar
  13. George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the Op. Res. Soc. of America, 2(4):393-410, 1954. Google Scholar
  14. Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O'Rourke. The Open Problems Project. URL: http://cs.smith.edu/~orourke/TOPP/.
  15. Sándor P. Fekete, Linda Kleist, and Dominik Krupke. Minimum scan cover with angular transition costs. In Symp. Comp. Geom. (SoCG), volume 164, pages 43:1-43:18, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.43.
  16. Sándor P. Fekete and Dominik Krupke. Covering tours and cycle covers with turn costs: Hardness and approximation. In Int. Conf. Algor. Complexity (CIAC), pages 224-236, 2019. Google Scholar
  17. Sándor P. Fekete and Dominik Krupke. Practical methods for computing large covering tours and cycle covers with turn cost. In Alg. Engin. Exp. (ALENEX), pages 186-198, 2019. Google Scholar
  18. Sándor P. Fekete and Gerhard J. Woeginger. Angle-restricted tours in the plane. Comp. Geom., 8:195-218, 1997. Google Scholar
  19. 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 Worksh. Graph Theo. Conc. Comp. Sci. (WG), pages 123-134, 2010. Google Scholar
  20. M. Gholami, M. Zandieh, and A. Alem-Tabriz. Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int. J. Adv. Manufact. Tech., 42(1-2):189-201, 2009. Google Scholar
  21. Haje Korth, Michelle F. Thomsen, Karl-Heinz Glassmeier, and W. Scott Phillips. Particle tomography of the inner magnetosphere. J. Geophys. Res.: Space Phys., 107(A9):SMP-5, 2002. Google Scholar
  22. Guoliang Li, Lining Xing, and Yingwu Chen. A hybrid online scheduling mechanism with revision and progressive techniques for autonomous Earth observation satellite. Acta Astronautica, 140:308-321, 2017. Google Scholar
  23. László Lovász. Coverings and colorings of hypergraphs. In Southeastern Conf. Combin., Graph Th., Comput. (SEICCGTC), pages 3-12, 1973. Google Scholar
  24. Clair E. Miller, Albert W. Tucker, and Richard A. Zemlin. Integer programming formulation of traveling salesman problems. J. ACM, 7(4):326-329, 1960. Google Scholar
  25. Rajeev Motwani and Joseph (Seffi) Naor. On exact and approximate cut covers of graphs. Technical report, Stanford University, Stanford, CA, USA, 1994. Google Scholar
  26. Andrei Novikov. PyClustering: Data mining library. J. Open Source Softw., 4(36):1230, 2019. Google Scholar
  27. Thomas J. Schaefer. The complexity of satisfiability problems. In Symp. Th. Comp. (STOC), pages 216-226, 1978. URL: https://doi.org/10.1145/800133.804350.
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 About DROPS Imprint Privacy Contact