Some robust inverse median problems on trees with interval costs

We address the problem of modifying vertex weights of a tree in such an optimal way that a given facility (vertex) becomes a 1-median in the modified tree. Here, each modifying cost receive any value within an interval. As the costs ar.e not exactly known, we apply the concept of absolute robust and minmax regret criteria to measure the cost functions. We first consider the absolute robust inverse 1-median problem with sum objective function. The duality of the problem helps to know the convexity of the induced univariate minimization problem. Based on the convexity, an $$O(n\log ^{2} n)$$ O ( n log 2 n ) time algorithm is developed, where n is the number of vertices on the underlying tree. We also apply the minmax regret criteria to the uncertain inverse 1-median problem with Chebyshev norm and bottleneck Hamming distance. It is shown that in the optimal solution there exists exactly one cost coefficient attaining the upper bound and the others attaining their lower bounds. Hence, we develop strongly polynomial-time algorithms for the problems based on this special property.