Recognising permuted Demidenko matrices

Eranda   Çela; Vladmir Deineko; Gerhard Johannes Wöginger

doi:10.1016/j.orl.2023.07.008

Recognising permuted Demidenko matrices

Eranda Çela ^*
, Vladmir Deineko
, Gerhard Johannes Wöginger

^*Korrespondierende/r Autor/-in für diese Arbeit

Institut für Diskrete Mathematik (5050)

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

Abstract

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

Originalsprache	englisch
Seiten (von - bis)	494-500
Seitenumfang	7
Fachzeitschrift	Operations Research Letters
Jahrgang	51
Ausgabenummer	5
DOIs	https://doi.org/10.1016/j.orl.2023.07.008
Publikationsstatus	Veröffentlicht - Sept. 2023

ASJC Scopus subject areas

Theoretische Informatik
Software
Angewandte Mathematik
Wirtschaftsingenieurwesen und Fertigungstechnik
Managementlehre und Operations Resarch

Fields of Expertise

Information, Communication & Computing

Zugriff auf Dokument

10.1016/j.orl.2023.07.008

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Recognising permuted Demidenko matrices
Çela , E. ., Deineko, V. & Woeginger, G., 2023, arXiv.
Publikation: Arbeitspapier › Preprint

Dieses zitieren

@article{24008ec8ecba49c4ae611c8b57c2a01a,

title = "Recognising permuted Demidenko matrices",

abstract = "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",

keywords = "Combinatorial optimization, Demidenko condition, Permuted Demidenko matrices, Travelling salesman problem",

author = "{\c C}ela , \{Eranda \} and Vladmir Deineko and W{\"o}ginger, \{Gerhard Johannes\}",

year = "2023",

month = sep,

doi = "10.1016/j.orl.2023.07.008",

language = "English",

volume = "51",

pages = "494--500",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

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 - https://www.scopus.com/pages/publications/85167810264

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 -

Recognising permuted Demidenko matrices

Abstract

ASJC Scopus subject areas

Fields of Expertise

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Publikationen

Recognising permuted Demidenko matrices

Dieses zitieren