Characterizing Permutation-Based Combinatorial Optimization Problems in Fourier Space
本文利用对称群上的傅里叶变换，将多种基于排列的组合优化问题投影到同一空间，描述了旅行商问题和线性排序问题的傅里叶系数，有助于理解问题间的联系并界定其内在维度。
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.