Christine Cheng's homepage

I'm an Assistant Professor at the Computer Science Department of the University of Wisconsin-Milwaukee . Prior to coming here in 2002, I was an Industrial Postdoctoral Associate at the Institute for Mathematics and its Applications (IMA), collaborating with research scientists at Telcordia Technologies. I received my Ph.D. from the Mathematical Sciences Department at Johns Hopkins University. My thesis advisor was Lenore Cowen.

Here is a picture of our little one, Madison Elle.

The Midwest Theory Day for Spring, 2009 will be held here at UWM on Saturday, April 25, 2009. If you're interested in CS Theory, come join us!

Contact Information

Teaching

Research Interests

My general interests lie at the intersection of computer science and discrete mathematics. The specifics, however, are continually changing! They typically fall under one of the following categories: Algorithm Design, Combinatorial Optimization, Combinatorics, and Graph Theory.

Papers

Stable Matchings

• C. Cheng and A. Lin, Stable Roommates Matchings, Mirror Posets, Median Graphs, and the Local/Global Median Phenomenon in Stable Matchings, submitted.
• C. Cheng, Understanding the Generalized Median Stable Matchings, accepted to Algorithmica.
  A preliminary version of this is The Generalized Median Stable Matchings: finding them is not that easy which appeared in the Proceedings of the 8th Latin American Theoretical Informatics (LATIN '08) (2008), Lecture Notes in Computer Science Vol. 4957, pp. 568-579.
• C. Cheng, E. McDermid, I. Suzuki, A Unified Approach to Finding Good Stable Matchings in the Hospitals/Residents Setting. Theoretical Computer Science 400:1-3(2008) pp.84-99.
• E. McDermid, C. Cheng, I. Suzuki, Hardness Results on the Man-Exchange Stable Marriage Problem with Short Preference Lists. Information Processing Letters 101:1(2007) pp. 13-19.

Distinguishing Numbers of Graphs

• C. Cheng, On Computing the Distinguishing and Distinguishing Chromatic Numbers of Interval Graphs and Other Results, accepted to Discrete Mathematics.
• V. Arvind, C. Cheng, N. Devanur, On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach. SIAM Journal of Discrete Mathematics 22:4(2008) pp.1297-1324.
• C. Cheng, On Computing the Distinguishing Numbers of Trees and Forests. Electronic Journal of Combinatorics 13:1(2006) R11.
• C. Cheng and L. J. Cowen, On Local Distinguishing Numbers of Cycles. Discrete Mathematics, 196:1-3(1999) pp.97-108.
• C. Cheng, Local Distinguishing Numbers of Trees . Congressus Numerantium, 133(1998) pp.21-30.

Generating Test Suites/Covering Arrays

• C. Cheng, The Test Suite Generation Problem: Optimal Instances and Their Implications . Discrete Applied Mathematics, 155:15(2007) pp.1943-1957.
• C. Cheng, A. Dumitrescu, P. Schroeder, Generating Small Combinatorial Test Suites to Cover Input-Output Relationships. Proceedings of 3rd Quality Software International Conference (QSIC '03) (2003) pp. 76-82. The following revised version contains corrections to the proceedings paper.

Declustering Schemes

• C.-M Chen and C. Cheng, From Discrepancy to Declustering:Near-optimal Multidimensional Declustering Strategies for Range Queries. Journal of the ACM, 51:1 (2004) pp.46-73. A preliminary version appeared in the Proceedings of Principles of Database Systems, (PODS '02) (2002) pp.29-38. Awarded "PODS 2002 Best Newcomer Paper".
• C.-M. Chen, C. Cheng, Replication and Retrieval Strategies of Multidimensional Data on Parallel Disks. Proceedings of the ACM Conference on Information and Knowledge Management (CIKM '03), (2003) pp. 32-39.

Others

• P. Haddawy, C. Cheng, N. Rujikeadkumjorn, K. Dhananaiyapergse, Balanced Matching of Buyers and Sellers in E-Marketplaces: The Barter Trade Exchange Model . Electronic Commerce Research and Applications 4:4(2005) pp. 299-314. A preliminary version of the paper appeared in the Proceedings of the 6th International Conference on Electronic Commerce (ICEC '04), (2004).
• C. Cheng, Improved Approximation Algorithms for the Demand Routing and Slotting Problem with Unit Demands on Rings. SIAM Journal of Discrete Mathematics 17:3(2004) pp. 384-402. A preliminary version appeared in the Proceedings of the 2nd Approximation Algorithms for Combinatorial Optimization (APPROX '99) (1999) pp.209-220.
• C. Cheng, H. Lemberg, S. Philip, E. van den Berg, T. Zhang, SLALoM: A Scalable Location Management Scheme for Large Mobile Ad-hoc Networks. Proceedings of Wireless Communications and Networking Conference (WCNC '02), (2002).
• C. Cheng, C.A. Duncan, M.T. Goodrich, K. Kobourov, Drawing Planar Graphs with Circular Arcs . Discrete and Computational Geometry, 25(2001) pp.405-418. A preliminary version appeared in the Proceedings of the 7th Symposium on Graph Drawing (GD '99) (1999) pp. 186-196.

Book Chapter

• C. Cheng, R. Jain and E. van den Berg, Location Prediction Algorithms for Mobile Wireless Systems. in Wireless Internet Handbook: Technologies, Standards and Applications, M. Ilyas and B. Furht (eds.) CRC Press, 2003, pp. 245-264.