Phd Seminars

Planning - Presentation - Archives

On the Kalai-Smorodinsky solutions for Bi-objective Spanning Tree Problem

May 29, 2024, 3 p.m. - Salle A104
Thanh Loan NGUYEN, Doctorante

This work investigates the Bi-objective Spanning Tree Problem (BSTP), an extension of the classical Minimum Spanning Tree problem with diverse applications. In this problem, each edge of a given graph is associated with two distinct weights, and the objective is to find a spanning tree that simultaneously minimizes the two total weights. As a specific case of bi-objective optimization, we may be interested in enumerating all the Pareto-optimal solutions of BSTP. However, as the number of Pareto-optimal solutions may be exponential, all the existing approaches to enumerate efficient solutions cannot achieve a polynomial CPU time. In this talk, we propose a novel approach for finding preferred efficient solutions where the worst of the ratios of the two objective values to their maximum possible values, respectively, is the minimum. This approach is based on the Kalai-Smorodinsky (KS) solution, a well-known concept in cooperative game theory. More precisely, we consider an extension of the KS solution concept to the discrete case that can be found by optimizing convex combinations of two objectives. We first characterize the properties of such KS solution(s) for the BSTP. Next, we present a weakly polynomial time algorithm for finding the KS solution(s) for the BSTP. Finally, we showcase the computational results in some instances and discuss the results. Beyond the particular case of the BSTP, this paper offers an efficient and explainable approach for solving bi-objective combinatorial optimization problems.