12-12-2013, 01:06 PM

We introduce the Upgrading Shortest Paths Problem, a new

combinatorial problem for improving network connectivity with a wide

range of applications from multicast communication to wildlife habitat

conservation. We define the problem in terms of a network with node

delays and a set of node upgrade actions, each associated with a cost and

an upgraded (reduced) node delay. The goal is to choose a set of upgrade

actions to minimize the shortest delay paths between demand pairs of

terminals in the network, subject to a budget constraint. We show that

this problem is NP-hard. We describe and test two greedy algorithms

against an exact algorithm on synthetic data and on a real-world instance

from wildlife habitat conservation. While the greedy algorithms can do

arbitrarily poorly in the worst case, they perform fairly well in practice.

For most of the instances, taking the better of the two greedy solutions

accomplishes within 5% of optimal on our benchmarks.

[ATTACHMENT NOT FOUND]

combinatorial problem for improving network connectivity with a wide

range of applications from multicast communication to wildlife habitat

conservation. We define the problem in terms of a network with node

delays and a set of node upgrade actions, each associated with a cost and

an upgraded (reduced) node delay. The goal is to choose a set of upgrade

actions to minimize the shortest delay paths between demand pairs of

terminals in the network, subject to a budget constraint. We show that

this problem is NP-hard. We describe and test two greedy algorithms

against an exact algorithm on synthetic data and on a real-world instance

from wildlife habitat conservation. While the greedy algorithms can do

arbitrarily poorly in the worst case, they perform fairly well in practice.

For most of the instances, taking the better of the two greedy solutions

accomplishes within 5% of optimal on our benchmarks.

[ATTACHMENT NOT FOUND]