EUVIMEDEUVIMED entdecken
Crossref

Characterizing Permutation-Based Combinatorial Optimization Problems in Fourier Space

Anne Elorza, Leticia Hernando, Jose A Lozano

Evolutionary Computation · 01.09.2023 · 31 (3) · 163-199

DOI: 10.1162/evco_a_00315 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, online erschienen am 01.09.2023. Verfasst von Anne Elorza und 2 weiteren Autor:innen. Beteiligte Einrichtung: Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián,…. Hauptthemen laut MEDLINE: Algorithms, Travel. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 29 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Comparing combinatorial optimization problems is a difficult task. They are defined using different criteria and terms: weights, flows, distances, etc. In spite of this apparent discrepancy, on many occasions, they tend to produce problem instances with similar properties. One avenue to compare different problems is to project them onto the same space, in order to have homogeneous representations. Expressing the problems in a unified framework could also lead to the discovery of theoretical properties or the design of new algorithms. This article proposes the use of the Fourier transform over the symmetric group as the tool to project different permutation-based combinatorial optimization problems onto the same space. Based on a previous study (Kondor, 2010), which characterized the Fourier coefficients of the quadratic assignment problem, we describe the Fourier coefficients of three other well-known problems: the symmetric and nonsymmetric traveling salesperson problem and the linear ordering problem. This transformation allows us to gain a better understanding of the intersection between the problems, as well as to bound their intrinsic dimension.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsTravel

Stichwörter der Autor:innen

Combinatorial optimization problemsFourier transformintrinsic dimensionpermutationsrepresentation theory

Autor:innen und Institutionen

  • Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain anne.elorza@ehu.eus.
  • Intelligent Systems Group, Department of Mathematics, University of the Basque Country UPV/EHU, 48940 Leioa, Spain leticia.hernando@ehu.eus.
  • Basque Center for Applied Mathematics (BCAM), 48009 Bilbao, Spain.
  • Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain ja.lozano@ehu.eus.

Zitieren

APA

Elorza, A., Hernando, L., & Lozano, J. A. (2023). Characterizing Permutation-Based Combinatorial Optimization Problems in Fourier Space. Evolutionary Computation, 31(3), 163-199. https://doi.org/10.1162/evco_a_00315

Vancouver

Elorza A, Hernando L, Lozano JA. Characterizing Permutation-Based Combinatorial Optimization Problems in Fourier Space. Evolutionary Computation. 2023;31(3):163-199. doi:10.1162/evco_a_00315

BibTeX
@article{Elorza2023,
  author = {Elorza, Anne and Hernando, Leticia and Lozano, Jose A},
  title = {Characterizing Permutation-Based Combinatorial Optimization Problems in Fourier Space},
  journal = {Evolutionary Computation},
  year = {2023},
  volume = {31},
  number = {3},
  pages = {163--199},
  doi = {10.1162/evco_a_00315}
}
Kostenlos starten →