Special cases of the quadratic shortest path problem

DOI10.1007/S10878-017-0219-9MaRDI QIDQ1743483zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hao Hu, Renata Sotirov

Publication date 13 April 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1611.07682

zbMATH Keywords

complexitydirected graphlinearizable instancesquadratic shortest path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: The quadratic shortest path problem (QSPP) is extcolor{black}{the problem of finding a path with prespecified start vertex $s$ and end vertex $t$ in a digraph} such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. We first consider a variant of the QSPP known as the adjacent QSPP. It was recently proven that the adjacent QSPP on cyclic digraphs cannot be approximated unless P=NP. Here, we give a simple proof for the same result. We also show that if the quadratic cost matrix is a symmetric weak sum matrix extcolor{black}{ and all $s$-$t$ paths have the same length,} then an optimal solution for the QSPP can be obtained by solving the corresponding instance of the shortest path problem. Similarly, it is shown that the QSPP with a symmetric product cost matrix is solvable in polynomial time. Further, we provide sufficient and necessary conditions for a QSPP instance on a complete symmetric digraph with four vertices to be linearizable. We also characterize linearizable QSPP instances on complete symmetric digraphs with more than four vertices. Finally, we derive an algorithm that examines whether a QSPP instance on the directed grid graph $G_{pq}$ ($p,qgeq2$) is linearizable. The complexity of this algorithm is $mathcalO(p^3{q}^2+p^2{q}^3)$.

Recommendations

• The quadratic shortest path problem: complexity, approximability, and solution methods
• On solving the quadratic shortest path problem
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• A class of exponential neighbourhoods for the quadratic travelling salesman problem
• Linearizable special cases of the QAP

Cites work

• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems
• A note on two problems in connexion with graphs
• A Theorem on Boolean Matrices
• Linear programming insights into solvable cases of the quadratic assignment problem
• Linearizable special cases of the QAP
• On the separation of split inequalities for non-convex quadratic integer programming
• QAPLIB - a quadratic assignment problem library
• The directed subgraph homeomorphism problem
• The quadratic shortest path problem: complexity, approximability, and solution methods
• The Variance-Constrained Shortest Path Problem
• The Wiener maximum quadratic assignment problem

Cited in

(12)

• The quadratic shortest path problem: complexity, approximability, and solution methods
• The linearization problem of a binary quadratic problem and its applications
• On the analysis of optimization problems in arc-dependent networks
• The quadratic cycle cover problem: special cases and efficient bounds
• Linearizable special cases of the quadratic shortest path problem
• On solving the quadratic shortest path problem
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems
• On the approximability of path and cycle problems in arc-dependent networks
• Arc-dependent networks: theoretical insights and a computational study
• A polyhedral characterization of linearizable quadratic combinatorial optimization problems
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems
• A class of exponential neighbourhoods for the quadratic travelling salesman problem

Describes a project that uses

Uses Software

• QAPLIB
• Algorithm 97

This page was built for publication: Special cases of the quadratic shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1743483)