Complexity of the multiobjective minimum weight minimum stretch spanner problem
Unternehmensforschung - Trang 1-19 - 2024
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