These problems arise in designing communication networks where a prespecified set of sites needs to be connected through a network.
Different applications judge the merit of the networks using different cost criteria.
We consider two such cost criteria. Under the first criterion, a network of minimum total edge-cost is to be designed. Both these problems are known to be NP-complete. Our algorithms output a network in polynomial time whose cost is within a small multiplicative factor of the minimum network cost. No approximation algorithms were previously known for either the generalized Steiner problem or the min-degree problem.