upgrading arc problem with budget constraint
Upgrading arcs are often used in transportation and telecommunication systems. In a real world situation, upgrading an arc between a pair of nodes corresponds to using a rapid mode of transit, such as using a plane instead of a truck between a pair of cities in a transportation network or using a higher speed cable between a pair of servers in a telecommunication network. These upgrades decrease transportation times through the network and can be critical in achieving delivery deadlines. This paper introduces and analyzes the upgrading arc problem with budget constraint. We show that this problem is NP-Complete in general and present several polynomially solvable cases.
np-completeness discount factor decision problem greedy selection diameter