Improved algorithms for joint optimization of facility locations and network connections
We study how to jointly optimize facility locations and their connections to clients. We develop an improved approximation algorithm based on a minimum spanning tree. When each vertex has a client, the problem is equivalent to matroid minimization. When all vertices are on a tree, the problem can be solved by dynamic programming.
facility location network connection approximation algorithm polynomial time algorithm steiner forest