Open Problems

Open problems posed in [IEEE Trans. Inform. Theory, 61 (2015), 3241-3250.]

Preliminary definitions (PDF)

Problem (1): Prove the nonexistence of perfect codes in S_n, using the Kendall τ-metric, for more values of n and/or other distances

Articles related to the Problem (1)

[1]Wang, X., Wang, Y., Yin, W. et al. Nonexistence of perfect permutation codes under the Kendall

τ

-metric. Des. Codes Cryptogr. 89, 2511–2531 (2021)

[2] A. Abdollahi, J. Bagherian, F. Jafari, M. Khatami, F.Parvaresh and R. Sobhani, New Bounds on the Size of Permutation Codes With Minimum Kendall T-distance of Three

Problem (2): What is the size of an optimal anticode in S_n with diameter D

Problem (3): Improve the lower bounds on the sizes of codes in S_n with even minimum Kendall τ-distance

Problem (4): Can the codes in S_5 and S_7 from Section V be generalized for higher values of n and to larger distances? Are these codes of optimal size

Articles related to the Problem (4)

Vijayakumaran, S. Largest Permutation Codes With the Kendall $\tau $ -Metric in $S_{5}$ and $S_{6}, IEEE Communications Letters, 20 (2016) 1912-1915

Note that the auther of the latter paper formulated the calculation of P(n, d) as a binary integer program with linear/quadratic constraints and found its value

for n ∈ {5, 6}. By using a solver (Gurobi Optimization Inc), the values of P(5, d) for d ∈ {3, 4, 5, 6} and P(6, d) for d ∈ {4, 5, . . . , 10} has been found successfully . But the solver has not been able to find the optimal value of P(6, 3) even after several weeks of computation. The solver has found a heuristic solution of cardinality 102 improving the lower bound on P(6, 3) from the previous value of 90. Click here to see 720 constraints of the optimization problem corresponding to P(6,3).

Date:

2023/01/13

Views:

Useful Link

All Rights of University of Isfahan are reserved.