On the minmax regret path median problem on trees

作者：

Highlights：

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

• An improved O(n2)-time algorithm is presented.

摘要

•We study the minmax regret path median 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.•An improved O(n2)-time algorithm is presented.

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

论文评审过程：Received 9 May 2014, Revised 3 December 2014, Accepted 7 January 2015, Available online 19 February 2015, Version of Record 10 June 2015.

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