Autor: Anne Elorza Deias

Tesis: Permutation-Based Combinatorial Optimization Problems in Fourier Space

Directores/as: Jose Antonio Lozano Alonso / Leticia Hernando Rodríguez

Día: 31 de enero de 2025
Hora: 11:00h
Lugar: sala Ada Lovelace (Facultad de Informática)

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."