Improved complexity results for the robust mean absolute deviation problem on networks with linear vertex weights

In a recent paper Lopez-de-los-Mozos et al. (2013), an algorithmic approach was presented for the robust (minmax regret) absolute deviation single-facility location problem on networks with node weights which are linear functions of an uncertain or dynamically changing parameter. The problem combines the mean absolute deviation criterion, which is the weighted average of the absolute deviations of individual customer-facility distances from the mean customer-facility distance and is one of the standard measures of “inequality” between the customers, with the minmax regret approach to optimization under uncertainty. The uncertain data are node weights (demands) which are assumed to change in a correlated manner being linear functions of a single uncertain parameter. The analysis in Lopez-de-los-Mozos et al. (2013) presented complexity bounds that are polynomial but too high to be of practical value. In this note, we present improvements of the analysis that significantly reduce the computational complexity bounds for the algorithm.