Approximation Algorithms for Budget Constrained Network Upgradeable Problems

Abstract

We study budget constrained network upgradeable problems. We are given an undirected edge weighted graph $G=(V,E)$ where the weight an edge $e\in E$ can be upgraded for a cost $c(e)$. Given a budget $B$ for improvement, the goal is to find a subset of edges to be upgraded so that the resulting network is optimum for $B$. 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 ${\mathcal{T}}^{{}^{\prime }}$ which is feasible within the budget $B$, such that $\mathrm{Pr}[l({\mathcal{T}}^{{}^{\prime }})\ge (1-\epsilon )\text{OPT}\text{ , }c({\mathcal{T}}^{{}^{\prime }})\le B]\ge 1-\frac{1}{n}$ (where $l$ and $c$ denote the length and cost of the tree respectively), for any fixed $\epsilon >0$, in time polynomial in $|V|=n$, $|E|=m$. Our results extend to the minimization version also. Previously Krumke et. al. \cite{krumke} presented a$(1+\frac{1}{\gamma },1+\gamma )$ bicriteria approximation algorithm for any fixed $\gamma >0$ 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 $n$ vertex DAG and give a $O(n^3)$ algorithm for the problem when there is a bound on the number of improvements allowed. We also give a $(1-\epsilon )$-approximation which runs in $O(\frac{n^4}{\epsilon })$ time for the budget constrained version. Similar results can be achieved also for the problem of shortest paths in a DAG.