Optimization of linear functions on cyclic permutations

Abstract

We consider the problem of minimizing a linear function on the set of cyclic permutations. The report proposes an accurate and heuristic solution to this problem. The concept of a partial permutation is presented, combinatorial properties of these permutations associated with the formation of new cycles are analyzed by adding a new element to a partial permutation. The corresponding sentences are formulated and proved. Рассматривается задача минимизации линейной функции на множестве циклических перестановок. В докладе предлагается точное и эвристическое решение этой проблемы. Представлена концепция частичной перестановки, анализируются комбинаторные свойства этих перестановок, связанные с формированием новых циклов, путем добавления нового элемента к частичной перестановке. Соответствующие предложения сформулированы и доказаны.