A classical approach to multicriteria problems asks for the optimization of a suitable linear combination of the objectives. In this work we address such problems when one of the objectives is the linear function, the other is a non-linear one and we seek for a spanning tree of a given graph which optimizes the combination of the two functions.We consider both maximization and minimization problems and present the complexity status of 56 such problems, giving, whenever possible, polynomial solution algorithms.
Combining Linear and Non Linear Objectives in Spanning Tree Problems / Dell'Amico, Mauro; F., Maffioli. - In: JOURNAL OF COMBINATORIAL OPTIMIZATION. - ISSN 1382-6905. - STAMPA. - 4:(2000), pp. 253-269. [10.1023/A:1009854922371]
Combining Linear and Non Linear Objectives in Spanning Tree Problems
DELL'AMICO, Mauro;
2000
Abstract
A classical approach to multicriteria problems asks for the optimization of a suitable linear combination of the objectives. In this work we address such problems when one of the objectives is the linear function, the other is a non-linear one and we seek for a spanning tree of a given graph which optimizes the combination of the two functions.We consider both maximization and minimization problems and present the complexity status of 56 such problems, giving, whenever possible, polynomial solution algorithms.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
