Author: Anne Elorza Deias

Thesis: Permutation-Based Combinatorial Optimization Problems in Fourier Space

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

Day: January 25, 2025
Time: 11:00h
Place: Ada Lovelace room (Computer Science Faculty)

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