Vortrag im Rahmen des Doctoral Seminar in Mathematics von Herrn Hao Hu (Tilburg University)

Thema: „A polynomial time algorithm for the linearization problem of the QSPP and its applications“

Kurzfassung: Given an instance of the quadratic shortest path problem (QSPP) on a digraph G, the linearization problem for the QSPP asks whether there exists an instance of the linear shortest path problem on G such that the associated costs for both problems are equal for every s-t path in G. We prove here that the linearization problem for the QSPP on directed acyclic graphs can be solved in O(nm^3) time, where n is the number of vertices and m is the number of arcs in G. By exploiting this linearization result, we introduce a family of lower bounds for the QSPP on acyclic digraphs. The strongest lower bound from this family of bounds is the optimal solution of a linear programming problem. To the best of our knowledge, this is the first study in which the linearization problem is exploited to compute bounds for the corresponding optimization problem. Numerical results show that our approach provides the best known linear programming bound for the QSPP.

Vortragende(r)
Hao Hu (Tilburg University)

Kontakt
Senka Haznadar (senka [dot] haznadar [at] aau [dot] at)