  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}^{'}$ which is feasible within the budget $B$, such
that $\Pr [ l(\mathcal{T}^{'}) \geq (1-\epsilon)\text{OPT}\text{ , }
c(\mathcal{T}^{'} ) \leq 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.
