News - Thesis/HDR announce

Date : Nov. 25, 2025, 9 a.m. - Type : Thesis - Thanhloan NGUYEN - salle A002

Bargaining solutions for biobjective combinatorial optimization and applications to some graph covering problems
In this thesis, we study the bi-objective combinatorial optimization (BOCO) problem and its applications to some graph covering problems. Our work investigates two main directions: (i) bargaining solutions for bi-objective combinatorial optimization problems and (ii) exact solutions for diverse versions of the spanning star forest problems which have numerous applications, especially in bioinformatics and automobile industry. 
In the first part, we study BOCO, which optimizes two conflicting objectives over a discrete feasible space. Since constructing the Pareto front is computationally expensive, we focus on fairness-based and mathematically well-defined selection criteria. Therefore, we analyze the Kalai-Smorodinsky (KS) solution in BOCO, provide formal definitions, examine its fundamental properties, and give a geometric description of the KS solution in the discrete space. We prove that the KS solution always exists and that there are at most two such solutions. We design a two-phase algorithm based on the binary search scheme, which has a logarithmic number of iterations. We introduce the price of fairness and test our approach on the Bi-objective Knapsack Problem and the Bi-objective Spanning Tree Problem, comparing KS solutions with Nash Fairness, Proportional Fairness, and Min-max solutions.
In the second part, we study a special case of BOCO, the Bi-objective Spanning Star Forest Problem (BSSFP), which minimizes both the number of centers and the total edge weight. We develop a two-phase dynamic programming framework relying on recursive formulations and Lagrangian relaxation, and we prove that all efficient solutions of this problem on trees can be enumerated in polynomial time. Finally, we provide a complete description of the spanning star forest polytope for 4-cactus graphs, extend it to general cactus graphs via projection, and address the separation problem for a specific family of inequalities.
 
Jury members:
- Mme. Hoai An LE THI, Professeure à l’Université de Lorraine (Rapporteure)
- M. Thibaut LUST, Maître de conférences HDR à Sorbonne Université (Rapporteur)
- Mme. Meltem Ozturk-Escoffier, Professeure à l’Université Paris-Dauphine (Examinatrice)
- M. Mourad BAIOU, Directeur de recherche au CNRS, LIMOS UMR 6158 (Examinateur)
- M. Paul WENG, Associate Professor à Duke Kunshan University, Chine (Examinateur)
- M. Viet Hung NGUYEN, Professeur à l’Université Clermont Auvergne (Directeur de thèse).