The Library
Recognising permuted Demidenko matrices
Tools
Cela, E., Deineko, Vladimir G. and Woeginger, G. (2023) Recognising permuted Demidenko matrices. Operations Research Letters, 51 (5). pp. 494-500. doi:10.1016/j.orl.2023.07.008 ISSN 0167-6377.
PDF
WRAP-recognising-permuted-Demidenko matrices-Deineko-2023.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only until 4 February 2025. Contact author directly, specifying your specific needs. - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (578Kb) |
Official URL: https://doi.org/10.1016/j.orl.2023.07.008
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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics T Technology > TS Manufactures |
||||||||
Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial optimization, Computer science -- Mathematics, Traveling-salesman problem, Mathematical statistics -- Data processing | ||||||||
Journal or Publication Title: | Operations Research Letters | ||||||||
Publisher: | Elsevier BV | ||||||||
ISSN: | 0167-6377 | ||||||||
Official Date: | September 2023 | ||||||||
Dates: |
|
||||||||
Volume: | 51 | ||||||||
Number: | 5 | ||||||||
Page Range: | pp. 494-500 | ||||||||
DOI: | 10.1016/j.orl.2023.07.008 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 1 August 2023 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |