In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. We first propose new and realistic models for both problems. Both problems are
-hard. We present the integer programming formulation of both problems and solve the linear programming (LP) relaxations approximately by the fast approximation algorithms for min-max resource-sharing problems in . For the global routing problem, we investigate particular properties of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally we develop asymptotic approximation algorithms for both problems depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for these problems.