Minimax regret spanning arborescences under uncertain costs
Minimax regret spanning arborescences under uncertain costs
复制标题
在不确定成本下跨越树状结构的最小最大遗憾
DOI：
10.1016/j.ejor.2006.07.036
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Candia
中科院分区：
文献类型：
--
作者：
E. Conde;A. Candia
本文考虑了弧成本部分已知的网络上的一个经典优化问题。假设对每个弧形成本给出区间估计，并且不知道关于弧形成本真值的统计分布的进一步信息。在这种情况下，给定网络中的一个跨越树，其成本可以根据每个单独的弧成本的选择，即根据不同的成本情景而呈现不同的值。我们分析了在每种可能的情况下，哪一种跨度树更接近最优跨度树的问题。最小极大后悔准则的提出就是为了得到该问题的稳健解。文中证明了贪婪算法可以在非循环网络上计算该问题的最优解。对于一般的网络，这个问题变成了NP难的。在这种情况下，优化问题的特殊结构允许我们为最优值设计一个边界过程，这将导致本文最后描述的启发式算法。
The paper considers a classical optimization problem on a network whose arc costs are partially known. It is assumed that an interval estimate is given for each arc cost and no further information about the statistical distribution of the truth value of the arc cost is known. In this context, given a spanning arborescence in the network, its cost can take on different values according to the choice of each individual arc cost, that is, according to the different cost scenarios. We analyze the problem of finding which spanning arborescence better approaches the optimal one under each possible scenario. The minimax regret criterion is proposed in order to obtain such a robust solution to the problem. In the paper, it is shown that a greedy-type algorithm can compute an optimal solution of this problem on acyclic networks. For general networks, the problem becomes NP-hard. In this case, the special structure of the optimization problem allows us to design a bounding process for the optimum value that will result in a heuristic algorithm described at the end of the paper.
影响因子：
--
作者：
PRIM, RC
通讯作者：
PRIM, RC