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.

Contact Information

Department of Electrical Engineering and Computer Science
University of Wisconsin-Milwaukee
3200 N. Cramer Ave.
Milwaukee, WI 53211
Phone: 414.229.5170
Fax: 414.229.2769
E-mail: ccheng at uwm dot edu

Teaching

Spring 2008	CS 535	Algorithm Design and Analysis
	CS 704	Analysis of Algorithms

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, E. McDermid, I. Suzuki, A Unified Approach to Finding Good Stable Matchings in the Hospitals/Residents Setting. Accepted to Theoretical Computer Science.
C. Cheng, The Generalized Median Stable Matchings: finding them is not that easy. Proceedings of the 8th Latin American Theoretical Informatics (LATIN '08) (2008), Lecture Notes in Computer Science Vol. 4957, pp. 568-579.
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

V. Arvind, C. Cheng, N. Devanur, On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach. Accepted to SIAM Journal of Discrete Mathematics.
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.

Last modified: Fri Apr 4 10:30:07 CDT 2008