EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Transforming Combinatorial Optimization Problems in Fourier Space: Consequences and Uses

Anne Elorza, Xabier Benavides, Josu Ceberio, Leticia Hernando, Jose A. Lozano

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →