We study budget constrained network upgradeable problems. We are given an undirected edge weighted graph @math where the weight an edge @math can be upgraded for a cost @math . Given a budget @math for improvement, the goal is to find a subset of edges to be upgraded so that the resulting network is optimum for @math . The results obtained in this paper include the following. Maximum Weight Constrained Spanning Tree We present a randomized algorithm for the problem of weight upgradeable budget constrained maximum spanning tree on a general graph. This returns a spanning tree @math which is feasible within the budget @math , such that @math (where @math and @math denote the length and cost of the tree respectively), for any fixed @math , in time polynomial in @math , @math . Our results extend to the minimization version also. Previously Krumke et. al. krumke presented a @math bicriteria approximation algorithm for any fixed @math for this problem in general graphs for a more general cost upgrade function. The result in this paper improves their 0 1 cost upgrade model. Longest Path in a DAG We consider the problem of weight improvable longest path in a @math vertex DAG and give a @math algorithm for the problem when there is a bound on the number of improvements allowed. We also give a @math -approximation which runs in @math time for the budget constrained version. Similar results can be achieved also for the problem of shortest paths in a DAG.
We consider the weight-reducible knapsack problem, where we are given a limited budget that can be used to decrease item weights, and we would like to optimize the knapsack objective value using such weight improvements. We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has an associated function C sub e that specifies the cost of shortening the edge by a given amount and that there is a budget B on the total reduction cost. The goal is to develop a reduction strategy satisfying the budget constraint so that the total length of a minimum spanning tree in the modified network is the smallest possible over all reduction strategies that obey the budget constraint. We show that in general the problem of computing optimal reduction strategy for modifying the network as above in NP-hard and present the first polynomial time approximation algorithms for the problem, where the cost functions C sub e are allowed to be taken from a broad class of functions. We also present improved approximation algorithms for the class of treewidth-bounded graphs when the cost functions are linear. Our results can be extended to obtain approximation algorithms for more general network design problems such as those considered in [GW, GG+94].  Given an undirected connected graph G and a cost function for increasing edge weights, the problem of determining the maximum increase in the weight of the minimum spanning trees of G subject to a budget constraint is investigated. Two versions of the problem are considered. In the first, each edge has a cost function that is linear in the weight increase. An algorithm is presented that solves this problem in strongly polynomial time. In the second version, the edge weights are fixed but an edge can be removed from G at a unit cost. This version is shown to be NP-hard. An Omega (1 log k)-approximation algorithm is presented for it, where k is the number of edges to be removed. In this paper, we consider the problem of how the transportation network can be modified most efficiently in order to improve the known location of the facilities. The performance of the facilities is measured by the “minisum” objective. We examine in the paper two types of network modifications: reductions and additions of links. We analyze various reduction and addition problems for both trees and general networks. For trees, we present exact results and algorithms for the majority of problems studied. For general networks, we discuss mainly heuristics.