| Many different-looking Network Design problems of which the optimal solutions which are expressed by the plannar geometric graphs. Therefore, the approximation many practical problems.; This thesis provides the polynomial time approximation algorithms for asks for the minimum number of Steiner points to interconnect the given points with the constant length edges. The ‘Grade of Service Steiner points’ problem asks for the minimum cost layout to interconnect the points, satisfying different requests. The ‘Interconnecting Highway’ problem asks for the shortest road layout to interconnect all the given disjoint segments. The algorithms produce the near-optimal solutions for many problems with the use of the infinitessimal error allowances to keep the computation time within polynomial bounds. If we divide the problem instance for the computation with the traditional way of ‘divide and concur’, the time complexity will grow exponentially because our problem is NP-hard. But our method spreads the infinitessimal error allowances properly to every range of the sub-problems so that we do not have to consider all the exponentially many cases.; Dynamic programmings have been applied for the optimization problems that hold the optimal substructure so that the global optimal solution can be acquired by combining locally optimized solutions. But many of the optimization problems do not hold such structure and have been approximated by the geometric analysis, i.e., forming a scheme on the geometric properties found. However, the analysis of the problems is so hard, and the approximation ratio to the optimal solution usually leaves a room to be improved: only a bit of improvement of the ratio for the same problem usually requires far different approaches with new ideas. Actually, the approximation algorithms of this thesis are the generalized dynamic programming that could work for the optimization problems which do not hold the optimal substructure , far reducing the analytic efforts. |
