Optimization Online


Special cases of the quadratic shortest path problem

Hao Hu(h.hu***at***tilburguniversity.edu)
Renata Sotirov(r.sotirov***at***uvt.nl)

Abstract: The quadratic shortest path problem (QSPP) is the problem of finding a path 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 or a symmetric product matrix, 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 on a directed cycle 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,q\geq 2$) is linearizable. The complexity of this algorithm is ${\mathcal{O}(p^{3}q^{2}+p^{2}q^{3})}$.

Keywords: quadratic shortest path problem, directed graph, linearizable instances

Category 1: Combinatorial Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Network Optimization


Download: [PDF]

Entry Submitted: 11/14/2016
Entry Accepted: 12/01/2016
Entry Last Modified: 11/14/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society