Transforming Combinatorial Optimization Problems in Fourier Space: Consequences and Uses
IEEE Transactions on Evolutionary Computation · 2025-08 · 29 (4) · 977-989
DOI: 10.1109/tevc.2024.3457268 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Evolutionary Computation, 2025-08. Verfasst von Anne Elorza und 4 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Eusko Jaurlaritza, Spanish Ministry of Economy and Competitiveness MINECO, University of the Basque Country UPV/EHU.
Abstract (Originalsprache)
We analyze three permutation-based combinatorial optimization problems in Fourier space, namely, the quadratic assignment problem, the linear ordering problem (LOP), and the symmetric and nonsymmetric traveling salesperson problem (STSP). In previous studies, one can find a number of theorems with necessary conditions that the Fourier coefficients of the aforementioned problems must satisfy. In this manuscript, we prove the sufficiency of these conditions, which implies that they constitute the exact characterization of the problems in Fourier space. In addition, the Fourier coefficients of the LOP and the symmetric and non-STSP are completely characterized by showing certain proportionality patterns that they must follow. Taking the characterization in Fourier space of the problems as a basis, we study classes of equivalent instances of the LOP and the symmetric and non-STSP, considering that two instances are equivalent if they have the same objective function. Furthermore, we give canonical representations for each problem in such a way that the input matrices have the minimum number of nonzero parameters.
Förderung
- Eusko Jaurlaritza
- Spanish Ministry of Economy and Competitiveness MINECO
- University of the Basque Country UPV/EHU
- Spanish Ministry of Science, Innovation and Universities
- Spanish Ministry of Science, Innovation and Universities through BCAM Severo Ochoa accreditation
Zitieren
APA
Elorza, A., Benavides, X., Ceberio, J., Hernando, L., & Lozano, J. A. (2025). Transforming Combinatorial Optimization Problems in Fourier Space: Consequences and Uses. IEEE Transactions on Evolutionary Computation, 29(4), 977-989. https://doi.org/10.1109/tevc.2024.3457268
Vancouver
Elorza A, Benavides X, Ceberio J, Hernando L, Lozano JA. Transforming Combinatorial Optimization Problems in Fourier Space: Consequences and Uses. IEEE Transactions on Evolutionary Computation. 2025;29(4):977-989. doi:10.1109/tevc.2024.3457268
BibTeX
@article{Elorza2025,
author = {Elorza, Anne and Benavides, Xabier and Ceberio, Josu and Hernando, Leticia and Lozano, Jose A.},
title = {Transforming Combinatorial Optimization Problems in Fourier Space: Consequences and Uses},
journal = {IEEE Transactions on Evolutionary Computation},
year = {2025},
volume = {29},
number = {4},
pages = {977--989},
doi = {10.1109/tevc.2024.3457268}
}
EUVIMED