. acm . cse . cuhk . library .

. home . about . research . teaching . life . photos .

 Ph.D. Thesis

On approximate min-max theorems for graph connectivity problems [ps] [pdf] University of Toronto, 2006 My current research interest is best illustrated by this thesis, where techniques from combinatorial optimization are used to design approximation algorithms for NP-hard graph theoretical problems.

 Combinatorial Optimization, Approximation Algorithms

On linear and semidefinite programming relaxation for hypergraph matching [ps] [pdf] Yuk Hei Chan, Lap Chi Lau Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010

Iterative rounding and relaxation [ps] [pdf] Lap Chi Lau, Mohit Singh RIMS Kokyuroku Bessatsu, Kyoto, 2009

Degree bounded network design with metric costs [ps] [pdf] Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 125-134, 2008

Additive approximation for bounded degree survivable network design [ps] [pdf] Lap Chi Lau, Mohit Singh Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 759-768, 2008

Degree bounded matroids and submodular flows [ps] [pdf] Tamás Király, Lap Chi Lau, Mohit Singh Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 259-272, 2008

Approximating minimum bounded degree spanning tress to within one of optimal [ps] [pdf] Mohit Singh, Lap Chi Lau Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 661-670, 2007

Survivable network design with degree or order constraints [ps] [pdf] Lap Chi Lau, Joseph Naor, Mohammad Salavatipour, Mohit Singh Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 651-660, 2007

Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs Tamás Király, Lap Chi Lau Journal of Combinatorial Theory, Series B, 98(6), 1233-1252, 2008 (Conference version appeared in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 283-292, 2006 [ps] [pdf])

Packing Steiner forests [ps] [pdf] Lap Chi Lau Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 362-376, 2005

An approximate max-Steiner-tree-packing min-Steiner-cut theorem [pdf] Lap Chi Lau Combinatorica, 27(1), 71-90, 2007 (Conference version appeared in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 61-70, 2004 [ps] [pdf]) Received the Machtey Award for best student paper

 Graph Algorithms

Computing graph roots without short cycles [pdf] Babak Farzad, Lap Chi Lau, Van Bang Le, Ngoc Tuy Nguyen Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), 397-408, 2009

A note on degree specified subgraphs [ps] [pdf] András Frank, Lap Chi Lau, Jácint Szabó Discrete Mathematics, 308, 2647-2648, 2008

Randomly colouring graphs with girth five and large maximum degree [ps] [pdf] Lap Chi Lau, Michael Molloy Proceedings of the 7th Latin American Symposium of Theoretical Informatics (LATIN), 656-676, 2006

Bipartite roots of graphs [pdf] Lap Chi Lau ACM Transactions on Algorithms, 2(2), 178-208, 2006 (Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 952-961, 2004 [ps] [pdf])

Recognizing powers of proper interval, split, and chordal graphs [ps] [pdf] Lap Chi Lau, Derek Corneil SIAM Journal on Discrete Mathematics, 18(1), 83-102, 2004

 Computer Networks

A constant bound on throughput improvement of multicast network coding in undirected networks [pdf] Zongpeng Li, Baochun Li, Lap Chi Lau IEEE Transactions on Information Theory, 55(3), 1016-1026, 2009

Conservative network coding [ps] [pdf] Nick Harvey, Kamal Jain, Lap Chi Lau, Chandra Nair, Yunnan Wu Proceedings of the 44th Annual Allerton Conference on Communications, Control, and Computing (Allerton), 2006

On achieving maximum multicast throughput in undirected networks [ps] [pdf] Zongpeng Li, Baochun Li, Lap Chi Lau IEEE Transactions on Information Theory, 52(6), 2467-2485, 2006 (24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2184-2194, 2005 [ps] [pdf])