| This thesis focuses on the design and application of approximation algorithms in computer and communication systems. Many problems in these computer and communication systems are known as NP-hard in combinatorial computation complexity theory. Several of them can be solved approximately using a common approximation theory approach: the combination of greedy, linear programming and randomization. We first extended the known approximation techniques and then applied the technique to several chosen problems.; Multifiber wavelength assignment problem is in optical communication infrastructure area, we applied the combined technique above and ran simulation based on the NSFNet and a randomly generated topology. Criticality driven session admission in Enterprise Resource Management Software is another example in computer software system that benefits from the proposed technique. Further, we applied the technique in communication network protocol design area and obtained best know result so far in balancing the cost and performance in minimum cost QoS multicasting.; Finally, we proposed a new polynomial time approximation algorithm to solve the operational version of Wavelength Assignment Problem. The new algorithm is in graph coloring form but is based on the core of Dantzig's simplex method: optimal is within the extreme points. We show that the computation complexity of this approach is O(N2W), which is as good as the existing sequential greedy algorithm in theory. Further, the simulation on randomly generated data set as well as NSFNet data set support the conclusion that the approximation factor of the proposed algorithm is close to that of the existing one. |
