Improved complexity results for the robust mean absolute deviation problem on networks with linear vertex weights
| Autor: | Marina Leal, Oded Berman, Igor Averbakh |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Vertex (graph theory)
050210 logistics & transportation Polynomial 021103 operations research Computational complexity theory Uncertain data Applied Mathematics 05 social sciences 0211 other engineering and technologies Regret 02 engineering and technology Minimax 0502 economics and business Discrete Mathematics and Combinatorics Applied mathematics Node (circuits) Weighted arithmetic mean Mathematics |
| Zdroj: | Discrete Applied Mathematics. 239:193-199 |
| ISSN: | 0166-218X |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect