Complexity of the multiobjective minimum weight minimum stretch spanner problem

Unternehmensforschung - Trang 1-19 - 2024
Fritz Bökler1, Henning Jasper1
1Dep. of Computer Science, Osnabrück University, Osnabrück, Germany

Tóm tắt

In this paper, we take an in-depth look at the complexity of a hitherto unexplored multiobjective minimum weight minimum stretch spanner problem; or in short multiobjective spanner (MSp) problem. The MSp is a multiobjective generalization of the well-studied minimum t-spanner problem. This multiobjective approach allows to find solutions that offer a viable compromise between cost and utility—a property that is usually neglected in singleobjective optimization. Thus, the MSp can be a powerful modeling tool when it comes to, e.g., the planning of transportation or communication networks. This holds especially in disaster management, where both responsiveness and practicality are crucial. We show that for degree-3 bounded outerplanar instances the MSp is intractable and computing the non-dominated set is BUCO-hard. Additionally, we prove that if $${\textbf{P}} \ne \textbf{NP}$$ , the set of extreme points cannot be computed in output-polynomial time, for instances with unit costs and arbitrary graphs. Furthermore, we consider the directed versions of the cases above.

Tài liệu tham khảo

Ahmed R, Hamm K, Latifi Jebelli MJ et al (2019) Approximation algorithms and an integer program for multi-level graph spanners. In: Kotsireas I, Pardalos P, Parsopoulos KE et al (eds) Analysis of experimental algorithms. Springer, Cham, pp 541–562 Althöfer I, Das G, Dobkin D et al (1993) On sparse spanners of weighted graphs. Discrete Comput Geom 9(1):81–100 Bang-Jensen J, Gutin G (2008) Digraphs: theory, algorithms and applications, 2nd edn. Springer monographs in mathematics. Springer, London Baswana S, Sen S (2007) A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct Algorithms 30(4):532–563 Bökler F (2018) Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem. PhD thesis, Technische Universität Dortmund Bökler F, Ehrgott M, Morris C et al (2017) Output-sensitive complexity of multiobjective combinatorial optimization. J Multi-Criteria Decis Anal 24(1–2):25–36 Bökler F, Ehrgott M, Rui Figueira J et al (2020) The output-sensitive complexity of the BUCO problem. Dagstuhl Rep 10(1):76–78. https://doi.org/10.4230/DagRep.10.1.52 Bökler F, Mutzel P (2015) Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. Algorithms—ESA 2015. Springer, Berlin, pp 288–299 Bökler F, Chimani M (2020) Approximating multiobjective shortest path in practice. In: SIAM ALENEX, pp 120–133 Brunsch T, Röglin H (2015) Improved smoothed analysis of multiobjective optimization. J ACM 62(1):4:1-4:58 Cai L (1994) NP-completeness of minimum spanner problems. Discrete Appl Math 48(2):187–194. https://doi.org/10.1016/0166-218X(94)90073-6 Cai L, Keil M (1994) Spanners in graphs of bounded degree. Networks 24(4):233–249. https://doi.org/10.1002/net.3230240406 Cai L, Corneil D (1995) Tree spanners. SIAM J Discrete Math 8(3):359–387. https://doi.org/10.1137/S08954801922374033 Caunhye A, Nie X, Pokharel S (2012) Optimization models in emergency logistics: a literature review. Socioecon Plann Sci 46(1):4–13 Cook S (1971) The complexity of theorem-proving procedures. In: ACM STOC, pp 151–158. https://doi.org/10.1145/800157.805047 Delling D, Pajor T, Werneck R (2015) Round-based public transit routing. Transp Sci 49(3):591–604 Diestel R (2017) Graph theory, vol 173. Graduate texts in mathematics. Springer, Berlin Ehrgott M (2005) Multicriteria optimization. Springer, Berlin Emelichev V, Perepelitsa V (1992) On cardinality of the set of alternatives in discrete many-criterion problems. Discrete Math Appl 2(5):461–471 Giantsoudi D, Grassberger C, Craft D et al (2013) Linear energy transfer-guided optimization in intensity modulated proton therapy: feasibility study and clinical potential. Int J Radiat Oncol Biol Phys 87(1):216–222 Hamacher H, Ruhe G (1994) On spanning tree problems with multiple objectives. Ann Oper Res 52(4):209–230 Hamacher H, Küfer K (1999) Inverse radiation therapy planning: a multiple objective optimisation approach. Monitoring evaluating. Planning health services. World Scientific, Singapore, pp 177–189 Hansen P (1980) Bicriterion path problems. Multiple criteria decision making theory and application, vol 177. Springer, Berlin, pp 109–127 Johnson DS, Yannakakis M, Papadimitriou CH (1988) On generating all maximal independent sets. Inf Process Lett 27(3):119–123 Kobayashi Y (2018) NP-hardness and fixed-parameter tractability of the minimum spanner problem. Theoret Comput Sci 746:88–97. https://doi.org/10.1016/j.tcs.2018.06.031 Kortsarz G, Peleg D (1994) Generating sparse 2-spanners. J Algorithms 17(2):222–236 Libotte G, Lobato F, Platt G et al (2020) Determination of an optimal control strategy for vaccine administration in COVID-19 pandemic treatment. Comput Methods Programs Biomed 196:105664 Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In: 41st IEEE FoCS, pp 86–92. https://doi.org/10.1109/SFCS.2000.892068 Peleg D, Schäffer A (1989) Graph spanners. J Graph Theory 13(1):99–116 Peleg D, Ullman J (1989) An optimal synchronizer for the hypercube. SIAM J Comput 18(4):740–747 Sigurd M, Zachariasen M (2004) Construction of minimum-weight spanners. Algorithms—ESA 2004. Springer, Berlin, pp 797–808 Thieke C, Küfer K, Monz M et al (2007) A new concept for interactive radiotherapy planning with multicriteria optimization: first clinical evaluation. Radiother Oncol 85(2):292–298 Wagner D, Zündorf T (2017) Public transit routing with unrestricted walking. In: ATMOS 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik