Publications

Computational Complexity

• J. Edmonds, C.K. Poon and D. Achlioptas, "Tight lower bounds for st-connectivity on the NNJAG model", SIAM J. Comput. 28(6): 2257-2284 (1999).
  Preliminary version: J. Edmonds and C.K. Poon, "A nearly optimal time-space lower bound for graph connectivity problem on NNJAGs", STOC'95, Las Vegas, pp147-156.
• C.K. Poon, "A space lower bound for st-connectivity on Node-named JAGs", Theoretical Computer Science 237(1-2): 327-345 (2000).
  Preliminary version: "Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs", FOCS'93, Palo Alto, pp218-227.
• C.K. Poon, "Verifying minimum stable circuit values" , Information Processing Letters 86(1): 27-32 (2003).
• P.Y. Lu, J.L. Zhang, C.K. Poon and J.Y. Cai, "Simulating undirected st-connectivity algorithms in JAGs and NNJAGs", ISAAC'05 , Hainan, China, December 2005, LNCS 3827, pp767-776.

Database, Text Mining and Web Searching

• C.K. Poon, "Dynamic orthogonal range queries in OLAP", Theoretical Computer Science. 296(3): 487-510 (2003).
  Preliminary version: "Orthogonal range queries in OLAP", ICDT'2001, London, LNCS 1973, pp361-374.
• C.K. Poon, "Optimal range max datacube for fixed dimensions", ICDT'2003., Siena, Italy, LNCS 2572, pp158-172.
• C.K. Poon and M. Chang, "An email classifier based on resemblance", 14th Int'l Symp. on Methodologies for Intelligent Systems , Maebashi City, Japan, 2003, LNAI 2871, pp344-348.
• C.H. Yuen, M. Chang, Y.K. Lai and C.K. Poon, "Excalibur: a personalized meta search engine", COMPSAC'04 fast abstract, pp49-50.
• M. Chang and C.K. Poon, "Catching the picospam", 15th Int'l Symp. on Methodologies for Intelligent Systems , Saratoga, New York, USA, May 2005, LNAI 3488, pp641-649.
• L. Yuen and C.K. Poon, "Relational index support for XPath axes", XSym'05, Trondheim, Norway, August 2005, LNCS 3671, pp84-98.
• M. Chang and C.K. Poon, "Efficient phrase querying with common phrase indexing", To appear in Information Processing and Management.
  Preliminary version: 28th European Conference on Information Retrieval (ECIR'06), London, April 2006, LNCS 3936, pp61-71.
• C.K. Poon and L. Yuen, "Faster twig pattern matching using extended Dewey ID", 17th International Conference on Database and Expert Systems Applications (DEXA'06) , Krakow, Poland, September 2006, LNCS 4080, pp297-306.

Scheduling

• Xiaotie Deng, C.K. Poon and Yuzhong Zhang, "Approximation algorithms in batch processing", J. of Combinatorial Optimizations. 7(3): 247-257 (2003).
  Preliminary version: ISAAC'99, Madras, LNCS 1741, pp153-162.
• C.K. Poon and Pixing Zhang, "Minimizing makespan in batch machine scheduling", Algorithmica 39(2):155-174 (2004).
  Preliminary version: ISAAC'00, Taipei, LNCS 1969, pp386-397.
• C.K. Poon and Wenci Yu, "A flexible on-line scheduling algorithm for batch machine with infinite capacity", Annals of Operations Research. 133(1-4): 175-181 (2005).
  Preliminary version: ICOTA'2001, Hong Kong, pp145-152.
• C.K. Poon and Wenci Yu, "On-line scheduling algorithms for a batch machine with finite capacity", Journal of Combinatorial Optimization. 9(2), pp167-186, 2005
  
• C.K. Poon and Wenci Yu, "Minimizing total completion time in batch machine scheduling", Int'l J. of Foundations of Computer Science 15(4):593-607 (2004).
  Preliminary version: In Proc. of MAPSP'2003, Aussois, France, pp69-70.
• F. Zheng, F. Chin, S. Fung, C.K. Poon and Y. Xu, "A tight lower bound for job scheduling with cancellation", Information Processing Letters 97(1):1-3, (2006).
• S.P.Y. Fung, F. Chin and C.K. Poon, "Laxity helps in broadcast scheduling", ICTCS'05, Siena, Italy, LNCS 3701, pp251-264.
• C.K. Poon, F. Zheng, and Y. Xu, "On-demand bounded broadcast scheduling with tight deadlines", In Proc. of CATS'06, Hobart, Australia, January 2006, pp139-143.
• F. Zheng, S.P.Y. Fung, W.T. Chan, F.Y.L. Chin, C.K. Poon and P.W.H. Wong, "Improved on-line broadcast scheduling with deadlines", In 12th International Computing and Combinatorics Conference (COCOON'06), Taipei, Taiwan, August 2006, LNCS 4112, pp320-329.
• S.P.Y. Fung, C.K. Poon and F.F. Zheng, "Online interval scheduling: randomized and multiprocessor cases", In 13th International Computing and Combinatorics Conference (COCOON'07), Banff, Canada, July 2007, LNCS 4598, pp176-186.

Computational Geometry

• C.K. Poon, Binhai Zhu and Francis Chin, "A polynomial time solution for labelling a rectilinear map", Information Processing Letters 65(4): 201-207 (1998).
  Preliminary version: SCG'97, Nice, pp451-453.
• Binhai Zhu and C.K. Poon, "Efficient approximation algorithms for two-label point labeling", Int'l J. of Computational Geometry and Applications 11(4): 455-464 (2001).
  Preliminary version: "Efficient approximation algorithms for multi-label map labeling", ISAAC'99 , Madras, LNCS 1741, pp143-152.

Algorithms and Data Structures

• Francis Chin and C.K. Poon, "A fast algorithm for computing longest common subsequences of small alphabet size", J. of Information Processing 13(4): 463--469 (1990).
  Preliminary version: Int'l Workshop on Discrete Algorithms and Complexity, Fukuoka, 1989, pp163-167.
• Francis Chin and C.K. Poon, "Performance analysis of some simple heuristics for computing longest common subsequences", Algorithmica 12(4/5): 293--311 (1994).
  Preliminary version: "Performance of heuristics for the longest common subseqeunces problem", Int'l Computer Symp., Taipei, 1990, pp164-169.
• Bethany Chan, Francis Chin and C.K. Poon, "Optimal simulation of full binary trees on faulty hypercubes", IEEE Trans. on Parallel and Distributed Systems 6(3): 269-286 (1995).
  Preliminary version: "Optimal specified root embedding of full binary trees in faulty hyerpcubes", 2nd Int'l Symp. on Algorithms, Taipei, 1992, LNCS 557, pp241-250.
• Valerie King, C.K. Poon, Vijaya Ramachandran and Santanu Sinha, "An optimal EREW PRAM algorithm for minimum spanning tree verification" , Information Processing Letters 62(3): 153-159 (1997).
• C.K. Poon and Vijaya Ramachandran, "A randomized linear work EREW PRAM algorithm to find a minimum spanning tree", Algorithmica 35(3): 257-268 (2003).
  Preliminary version: ISAAC'97, Singapore, LNCS 1350, pp212-222.
• C.K. Poon and A. Kwok, "Two-dimensional packet classification and filter conflict resolution in the Inernet", To appear in Theory of Computing Systems.
  Preliminary version: "Space optimal packet classification for 2-d conflict-free filters", I-SPAN'04, Hong Kong, pp260-265.
• C.K. Poon and W.K. Yiu, "Opportunistic data structures for range queries", Journal of Combinatorial Optimization 11(2): 145-154 (2006).
  Preliminary version: COCOON'05 , Kunming, China, August 2005, LNCS 3595, pp560-569.
• Y.K. Lai, C.K. Poon and Benyun Shi, "Approximate colored range queries and point enclosure queries", To appear in Journal of Discrete Algorithms.
  Preliminary version: "Approximate colored range queries", ISAAC'05 , Hainan, China, December 2005, LNCS 3827, pp360-369.
• H. Sun and C.K. Poon, "Two improved range-efficient algorithms for F0 estimation", In 4th International Conference of Theory and Applications of Models of Computation (TAMC'07), Shanghai China, May 2007, LNCS 4484, pp659-669.