Facility location problem with a cost function
The problem you're asking to solve is a variant of the $k$-median problem on a metric space. You haven't mentioned anything about the various sizes involved, but as a formal matter, there are only $n$ choices for the magic number $k$ (the number of centers), and so after "guessing" the right value of $k$, you can run any of the standard approximation algorithms for $k$-median in graphs (your graph is a complete graph). In particular, one such is the method by Jain and Vazirani. 

There's an older technique by Lin and Vitter that says that if you're willing to expand the number of centers by a tiny amount, you can get a pretty good approximation to the cost (w.r.t optimal centers).