Analyzing the Fourier Representation of Permutation-Based Combinatorial Optimization Problems
Jose Antonio Lozano · 2023
Combinatorial optimization seeks to uncover efficient algorithms for solving complex problem instances. While achieving the ultimate goal of universal optimization remains a challenge, progress in this direction yields valuable insights for the field. A critical initial step involves taxonomizing problems and instances through a common representation. In this presentation, we employ the Fourier transform framework to investigate permutation-based combinatorial optimization problems. Specifically, we examine the Fourier coefficients of various special cases of the quadratic assignment problem, revealing their inherent characteristics. Leveraging this decomposition, we explore the transition of the linear ordering problem from being tractable (P) to becoming NP-hard, shedding light on the intricacies of this transformation. Through this analysis, we advance our understanding of permutation-based combinatorial optimization, paving the way for potential algorithmic breakthroughs.