Minmax Regret 1-Facility Location on Uncertain Path Networks

摘要

Let P be an undirected path graph of n vertices. Each edge of P has a positive length and a constant capacity. Every vertex has a nonnegative supply, which is an unknown value but is known to be in a given interval. The goal is to find a point on P to build a facility and move all vertex supplies to the facility such that the maximum regret is minimized. The previous best algorithm solves the problem in O(n log~2 n) time and O(n log n) space. In this paper, we present an O(n log n) time and O(n) space algorithm, and our approach is based on new observations and algorithmic techniques.