Egilea: Anne Elorza Deias

Izenburua: Permutation-Based Combinatorial Optimization Problems in Fourier Space

Zuzendariak: Jose Antonio Lozano Alonso / Leticia Hernando Rodríguez

Eguna: 2025ko urtarrilaren 31n
Ordua: 11:00h
Tokia: Ada Lovelace aretoa (Informatikako fakultatea)

Abstract:

"In this thesis, permutation-based combinatorial optimization problems are analyzed under a fairly uncommon framework: Fourier space. We give the Fourier characterization of three problems: the quadratic assignment problem, the linear ordering problem and the traveling salesperson problem. Then, the definition of these problems in Fourier space is used to reveal a number of properties that remained unseen with their usual definition. Among others, the topics of intrinsic dimension, intersection between problems, equivalent instances and rankings produced by the problems are studied. The Fourier decomposition of the linear ordering problem is also used to decompose the problem into a P and an NP-hard component. Using this decomposition, it is experimentally observed how the behavior of a number of constructive algorithms degrades as the problem transits from P to NP-hardness."