Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/314960 
Erscheinungsjahr: 
2024
Quellenangabe: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 100 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2024 [Pages:] 65-83
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
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 P≠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.
Schlagwörter: 
Multiobjective optimization
Graph spanners
Output-sensitive complexity
Extreme points
Parametric optimization
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.