Prof. Frits Spieksma, Eindhoven University of Technology
Chair: Prof. Carlo Filippi, Università di Brescia
When: April 29th, 2026, 2:30 PM
Where: Room D2, Brixia Building, via San Faustino 64
We describe a framework for quantifying the trade-off between diversity and optimality in combinatorial optimization problems, which we refer to as the Price of Diversity (PoD).
We apply this concept to the Traveling Salesman Problem (TSP) with the triangle inequality, and show how the demand for multiple diverse solutions influences tour quality. Specifically, we consider the problem of finding two edge-disjoint tours while minimizing the length of the longer tour. For this setting, we show that the PoD, is asymptotically 8/5 in a (special) one-dimensional case and exactly 2 in general.
We also consider a stricter form of diversity for the TSP and connect the resulting problem to placing queens on a chess board.