×

Special cases of the quadratic shortest path problem. (English) Zbl 1396.90094

Summary: The quadratic shortest path problem (QSPP) is 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 \(\mathrm {P}=\mathrm {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 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,q\geq 2\)) is linearizable. The complexity of this algorithm is \(\mathcal {O}(p^{3}q^{2}+p^{2}q^{3})\).

MSC:

90C35 Programming involving graphs or networks

Software:

QAPLIB; Algorithm 97
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adams W, Waddell L (2014) Linear programming insights into solvable cases of the quadratic assignment problem. Discrete Optim 14:46-60 · Zbl 1308.90085 · doi:10.1016/j.disopt.2014.07.001
[2] Buchheim C, Traversi E (2015) Quadratic 0-1 optimization using separable underestimators. Optimization online · Zbl 1308.90120
[3] Burkard RE, Karisch SE, Rendl F (1997) Qaplib—a quadratic assignment problem library. J Global Optim 10(4):391-403 · Zbl 0884.90116 · doi:10.1023/A:1008293323270
[4] Çela E, Schmuck NS, Wimer S, Woeginger GJ (2011) The wiener maximum quadratic assignment problem. Discrete Optim 8(3):411-416 · Zbl 1233.90282 · doi:10.1016/j.disopt.2011.02.002
[5] Çela E, Deineko VG, Woeginger GJ (2016) Linearizable special cases of the qap. J Comb Optim 31(3):1269-1279 · Zbl 1344.90053 · doi:10.1007/s10878-014-9821-2
[6] Ćustić A, Punnen A (2017) A characterization of linearizable instances of the quadratic minimum spanning tree problem. J Comb Optim https://doi.org/10.1007/s10878-017-0184-3 · Zbl 1394.90544
[7] Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269-271 · Zbl 0092.16002 · doi:10.1007/BF01386390
[8] Floyd RW (1962) Algorithm 97: shortest path. Commun ACM 5(6):345 · doi:10.1145/367766.368168
[9] Fortune S, Hopcroft J, Wyllie J (1980) The directed subgraph homeomorphism problem. Theoret Comput Sci 10(2):111-121 · Zbl 0419.05028 · doi:10.1016/0304-3975(80)90009-2
[10] Hu H, Sotirov R (2017) The QSPP linearization problem on DAGs and its applications. Working paper · Zbl 1344.90053
[11] Murakami K, Kim HS (1997) Comparative study on restoration schemes of survivable ATM networks. In: INFOCOM’97. Sixteenth annual joint conference of the IEEE computer and communications societies. Driving the information revolution., Proceedings IEEE. vol 1. IEEE, pp 345-352 · Zbl 0884.90116
[12] Nie YM, Wu X (2009) Reliable a priori shortest path problem with limited spatial and temporal dependencies. In: Transportation and traffic theory 2009: golden jubilee. Springer, pp 169-195 · Zbl 1069.90520
[13] Punnen AP, Kabadi SN (2013) A linear time algorithm for the koopmans-beckmann qap linearization and related problems. Discrete Optim 10(3):200-209 · Zbl 1506.90232 · doi:10.1016/j.disopt.2013.02.003
[14] Rostami B, Malucelli F, Frey D, Buchheim C (2015) On the quadratic shortest path problem. In: International symposium on experimental algorithms. Springer, pp 379-390 · Zbl 0419.05028
[15] Rostami B, Chassein A, Hopf M, Frey D, Buchheim C, Malucelli F, Goerigk M (2016) The quadratic shortest path problem: complexity, approximability, and solution methods. Optimization online · Zbl 1403.90645
[16] Sen S, Pillai R, Joshi S, Rathi AK (2001) A mean-variance model for route guidance in advanced traveler information systems. Transp Sci 35(1):37-49 · Zbl 1069.90520 · doi:10.1287/trsc.35.1.37.10141
[17] Sivakumar RA, Batta R (1994) The variance-constrained shortest path problem. Transp Sci 28(4):309-316 · Zbl 0823.90130 · doi:10.1287/trsc.28.4.309
[18] Warshall S (1962) A theorem on boolean matrices. J ACM 9(1):11-12 · Zbl 0118.33104 · doi:10.1145/321105.321107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.