TY - JOUR
T1 - Recognising permuted Demidenko matrices
AU - Çela , Eranda
AU - Deineko, Vladmir
AU - Wöginger, Gerhard Johannes
PY - 2023/9
Y1 - 2023/9
N2 - We solve the recognition problem for permuted Demidenko matrices. This problem is relevant in the context of hard combinatorial optimization problems becoming tractable if the input is a Demidenko matrix. For example the TSP is polynomially solvable for Demidenko distance matrices. In the TSP context we look for a renumbering of the cities resulting in a Demidenko distance matrix, thus in a polynomially solvable case. We can find such a renumbering of n cities in O (n4) time, if it exists
AB - We solve the recognition problem for permuted Demidenko matrices. This problem is relevant in the context of hard combinatorial optimization problems becoming tractable if the input is a Demidenko matrix. For example the TSP is polynomially solvable for Demidenko distance matrices. In the TSP context we look for a renumbering of the cities resulting in a Demidenko distance matrix, thus in a polynomially solvable case. We can find such a renumbering of n cities in O (n4) time, if it exists
KW - Combinatorial optimization
KW - Demidenko condition
KW - Permuted Demidenko matrices
KW - Travelling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=85167810264&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2023.07.008
DO - 10.1016/j.orl.2023.07.008
M3 - Article
SN - 0167-6377
VL - 51
SP - 494
EP - 500
JO - Operations Research Letters
JF - Operations Research Letters
IS - 5
ER -