Permutation-Based Combinatorial Optimization Problems in Fourier Space

• Autores: Anne Elorza Deias
• Directores de la Tesis: José Antonio Lozano Alonso (dir. tes.) , Leticia Hernando Rodríguez (codir. tes.)
• Lectura: En la Universidad del País Vasco - Euskal Herriko Unibertsitatea ( España ) en 2025
• Idioma: inglés
• Enlaces
  • Tesis en acceso abierto en: ADDI
• Resumen

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