【摘要】 讨论了在l1范数下的反瓶颈Steiner树问题.对于给定的一个可行解,修改带限制的边权使其成为瓶颈Steiner树问题的最优解,并且在l1范数下边权的修改费用最小.讨论了最优目标值的范围,在此基础上给出了一个求解反瓶颈Steiner问题的多项式时间算法.更多还原

【Abstract】 In this paper,we consider the inverse bottleneck Steiner tree problem under the l1 norm.The work is to modify the constraint weights so that a given feasible solution becomes an optimal solution of a bottleneck Steiner tree problem,and the deviation of the costs,measuered by the l1 norm,is minimum.We discuss the interval of the optimal value,and present strongly polynomial time algorithm to solve the inverse bottleneck Steiner tree problem.更多还原