Some inverse min-max network problems under weighted l1 and l∞ norms with bound constraints on changes |
| |
Authors: | Xiaoguang Yang and Jianzhong Zhang |
| |
Institution: | (1) Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100080, China;(2) Department of System Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong, China |
| |
Abstract: | We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound
constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the
deviation of the weights, measured by the weighted l
1 norm or weighted l
∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree
problem and the inverse maximum capacity path problem. |
| |
Keywords: | Inverse min-max network problem Weighted l 1 norm Weighted l∞ norm Bound constraints Polynomial time algorithms |
本文献已被 SpringerLink 等数据库收录! |
|