Shortest path in complete bipartite digraph problem and its applications

We introduce the shortest path in complete bipartite digraph (SPCB) problem: Given a weighted complete bipartite digraph G = (X, Y, E) with X = {x₀,..., x_n} and Y = {y₀,..., y_m}, find a shortest path from x₀ to x_n in G. For arbitrary weights, the problem needs at least Ω(nm) time to solve. We show if the weight matrices are concave, the problem can be solved in O(n+m log n) time. As applications, we discuss the traveling salesman problem for points on a convex polygon and the minimum latency tour problem for points on a straight line. The known algorithms for both problems require Θ(n²) time. Using our SPCB algorithm, we show they can be solved in O(n log n) time. These results solve two open questions posed by Marcotte and Suri; and by Afrati et al.