An improved algorithm for the minmax regret path centdian problem on trees

作者：

Highlights：

• We study the minmax regret path centdian 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.

• The previous upper bound is O(n5log⁡n).

• This paper gives an improved O(n4)-time algorithm.

摘要

•We study the minmax regret path centdian 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.•The previous upper bound is O(n5log⁡n).•This paper gives an improved O(n4)-time algorithm.

论文关键词：Location theory,Minmax regret optimization,Medians,Centers,Centdians,Trees

论文评审过程：Received 28 November 2016, Revised 6 May 2018, Accepted 18 May 2018, Available online 28 June 2018, Version of Record 13 August 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.05.003