Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/314960 
Year of Publication: 
2024
Citation: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 100 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2024 [Pages:] 65-83
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
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.
Subjects: 
Multiobjective optimization
Graph spanners
Output-sensitive complexity
Extreme points
Parametric optimization
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.