On the minmax regret path median problem on trees

•We study the minmax regret path median problem on a tree.•The weight of each vertex is uncertain and is characterized by an interval.•It is required to find a solution minimizing the worst-case loss.•An improved O(n2)O(n2)-time algorithm is presented.

This paper studies the problem of finding the path median on a tree in which vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. An O(n2)O(n2)-time algorithm is presented, improving the previous upper bound from O(n4)O(n4).