Congratulation to Mr. Yung Chun Kong, a MPhil student supervised by Prof. Lau Lap Chi, has been selected as the winner of the Faculty’s Outstanding Thesis Award 2009.
Mr. Yung’s thesis entitled “Edge Splitting-off and Network Design Problems” is motivated by the degree bounded network design problem. This problem captures some key problems in combinatorial optimization and it also has practical applications in various areas as well. However, it does not admit any polynomial factor approximation algorithm, since the feasibility problem is NP-Hard even for simple case such as finding a spanning tree.
In this thesis, he shows that under metric cost, there are constant factor approximation algorithms for various degree bounded network design problems. The main technical tool in these algorithms is a combinatorial operation, known as edge splitting-off. Apart from network design, this technique is also widely-used in some other edge-connectivity problems. By extending and improving some edge splitting-off results, we develop efficient edge splitting-off algorithms that improve the time complexity of the best known result by a factor of ?�[(n). These algorithms are conceptually very simple and can be extended to different settings. Moreover, he also extends edge splitting-off to incorporate some additional constraints and apply these results to give additive approximation algorithms for several constrained connectivity augmentation problems.
