Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client demands a package of weight $w_i$ and is $d(r,i)$ distance away. Two clients $i,j$ are $d(i,j)$ distance away. Initially, all the packages are at the root.
Now we will deliver these packages and we can carry at most $W$ weight during delivery. Once delivered, we will have to come back to the root again and collect more packages and deliver again until all the packages have been delivered. We are given the weights of all packages and also the set of all distances. Our goal is to find the shortest route. Design a constant factor approximation algorithm for a tree.
By this, I mean that $r$ is the root of the tree and the clients are at the other nodes of the tree including the leaves of the tree, i.e. there are $n$ nodes. We need to design the shortest route. Note that we are not going to visit each client only once because of the tree structure. (If we only think of the clients as the leaves of the tree and say there are $n$ nodes, then is the problem equivalent? I don't know.)
I have found this link that talks about the general problem: http://dimacs.rutgers.edu/programs/challenge/vrp/vrpsd/
But since my graph is only a tree, it should be much easier to give a constant factor approximation algorithm. Any help will be appreciated.
