Research
Areas of Interest
My research interests include combinatorial optimization, integer programming and network analysis.
Since my research interests are in the intersection of discrete mathematics and theoretical computer science, my papers are tracked by mathscinet and/or computer science data bases.
mathscinet (Subscription is required.)
Scopus (Subscription is required.)
zbMATH (Subscription is required.)
Background and Current Activities
I went to graduate school at the University of Waterloo in 1988 after graduated from Memorial University of Newfoundland with a B.Sc. (Hons) in Mathematics. I was in the Department of Combinatorics and Optimization within the Faculty of Mathematics. For my master degree, I worked on design theory under the supervision of Ron Mullin. After my M.Math., it took me a while to decide which area I wanted to work on. I considered design theory, portfolio analysis and enumeration. However, after I took a course in combinatorial optimization from Bill Cunningham, I decided discrete optimization is the area for me.
I completed my Ph.D. thesis titled Wheel Inequalities for Stable Set Polytopes under the supervision of Bill Cunningham and graduated from the University of Waterloo in 1995. Besides Bill, my internal thesis committee members were Levent Tunçel, Charlie Colbourn and Anna Lubiw, and the external committee member was Daniel Bienstock from Columbia University. In my thesis, I found large classes of separable and high-dimensional faces for stable set polytopes. Besides my thesis research, I also worked on augmentation problems. I started the research after I read a wonderful paper by András Frank. As an added bonus, András invited me to a workshop in Budapest in 1994.
From 1995 to 1997, I was a Natural Sciences and Engineering Research Council of Canada Postdoctoral Fellow and part-time lecturer in the Department of Computational and Applied Mathematics within the George R. Brown School of Engineering at Rice University . During this time, I learned the computational aspects of discrete optimization from Bob Bixby, Bill Cook and David Applegate. I worked on two projects while I was at Rice University. The first one was on the computational issues of separating subdivision of bicycle wheel inequalities over the cut polytopes. The second one, through joint work with Jennifer Rich, was to look at a home health care routing and scheduling problem.
In 1997, I had to make a tough career decision. I was offered a job at Southern Energy in Atlanta and a tenure-track job at Oakland University. Although the offer from Southern Energy was better financially, I decided that an academic job will be better for me.
Since I came to Oakland University, my main research focuses on stable set polytopes and interconnection networks. The stable set problem is a fundamental NP-Complete problem as it was the second problem considered in the seminal paper of Stephen Cook published in 1971. For this problem, through joint work with Sven de Vries, we were able to extend some results from my thesis by finding new, tight and separable inequalities. An interconnection network is the underlying architecture for building parallel processing machines. My interest lies in the structural properties of these networks such as connectivity problems, routing algorithms and vulnerability issues. This continuing project is in collaboration with Marc Lipman. Students Will Lindsey, Ray Kleinberg and Dan Steffy joined us for a couple of projects (2003 - 2004). Ray Kleinberg now works at US Army TACOM LCMC, Will Lindsey earned his Ph.D. at Purdue and Dan Steffy graduated from Georgia Tech with Ph.D. in Algorithm, Combinatorics and Optimization. László Lipták and I have worked closely in this area since 2005.
Some of the other projects that I have looked at or have tried (some finished, some ongoing, some unsuccessful) include time-stamped collaboration graphs (with Marc Lipman and Jerry Grossman), polyhedral properties of optimal search trees (with Curt Chipman), sphere-of-influence graphs (with Marc Lipman and Serge Kruk), student scheduling problem (with Marc Lipman and Serge Kruk), splitting Eulerian tour (with Datta Kulkarni, Jerry Grossman and David Pike), scheduling of examinations (with Ray Kleinberg, Serge Kruk, Will Lindsey and Dan Steffy), and integer formulation of NHL playoff determination (with Dan Steffy).
In 2003, my first Ph.D. student, Lazaros Kikas defended his Ph.D. thesis in the area of interconnection networks. He is currently an associate professor at the University of Detroit Mercy. In 2007, my second Ph.D. student, Nart Shawash defended his Ph.D. thesis in the area of interconnection networks. He is currently an associate professor at the University of Detroit Mercy. In 2013, my third Ph.D. student, Rob Connolly defended his Ph.D. thesis in the area of interconnection networks. In 2015, my fourth Ph.D. student, Mohamad Abdallah defended his Ph.D. thesis in the area of interconnection networks. He is currently an assistant professor at the American University of Kuwait. In 2019, my fifth Ph.D. student, Chris Melekian defended his Ph.D. thesis in the area of interconnection networks, winning the Outstanding Dissertation Award (STEM). He started working at General Motors in 2019.
Last updated on February 26, 2021
Unpublished Technical Report
E. Cheng and J.L. Rich. "A home health care routing and scheduling problem." TR98-04
List of coauthors (chronological order)
(For an alphabetical list, click here.)
William H. Cunningham
Tibor Jordán
Jennifer L. Rich
Marc J. Lipman
Alan Park
Sven de Vries
Jerrold W. Grossman
Serge G. Kruk
Yuyin Chen
Daniel E. Steffy
William A. Lindsey
Raymond P. Kleinberg
Lazaros D. Kikas
László Lipták
Meelap Shah
Jong-Seok Kim
Hyeong-Ok Lee
Nart Shawash
David Stiebel
Linda Lesniak
Zhizhang Shen
Ke Qiu
Lih-Hsing Hsu
Cheng-Kuan Lin
Jimmy J.M. Tan
Fred Sala
David Sherman
Shuhong Gao
Sarah Anderson
Kelly Christensen
Jennifer Diemunsch
Matthew Toeniskoetter
Ram Bhaskar
Mason Liang
Saurabh Pandey
Kevin Wang
Brian Scholten
James Voss
Randy Jia
David Lu
Sung-Won Kim
Roger Jia
Philip Hu
Ming Tsai
Christopher Gillies
Nilesh Patel
Gautam Singh
George Wilson
Weihua Yang
Zhao Zhang
Xiafeng Guo
Allen Yuan
Allen Chen
Rolland He
Tung-Yang Ho
Sachin Padmanabhan
Philip Bonneville
Joseph Renzi
Chun-Nan Hung
Shalin Shah
Vyom Shah
Akhil Nistala
Brian Xu
Steven Cheng
Dhruv Medarametla
Lawrence Wu
Aaron Zeng
Mohamad Abdallah
Cheng-Chang Yang
Sun-Yuan Hsieh
Nai-Wen Chang
Justin Kelm
Roi Orzach
Robert Connolly
Christopher Melekian
William Chang
Sang-Ho Shim
Li Li
Omer Siddiqui
Yaping Mao
Zhao Wang
Zhiwei Guo
Colton Magnant
Ajay Arora
Keivan Noroozi
Karimah Sweet
Zachary Wheeler
Dana Ferranti
Kathik Nataraj
Meng-Chien Yang
Shengjie He
Rong-Xia Hao
Tianlong Ma
Sai Anantapantula
Stephanie Budzisz
Maryam Khosravi
Shu-Li Zhao
Spencer Liu
Chittesh Thavamani
Freddie Zhao
Jinling Wang
Jinyu Zou
Xiaxia Guan
Lina Xue
Mei-Mei Gu
Jing Li
Shurong Zou
Guanqin Lian
Shuming Zhou
Jiafei Liu
Gaolin Chen
Zhendong Gu
Ping Han
Jie-Fu Huang
Xujing Li
Nan Jia
Timothy Wu
Daniel Tian
Xu Wang
Qianru Zhou
Xiaoqing Liu
Ming Li
Sambhav Gupta
Limei Lin
Yanze Huang
Li Xu
Hong Zhang
Qifan Zhang
Saranya Anantapantula
Abhishek Vangipuram
Gary Chartrand
Ping Zhang
Ethan Gibbons
Longkun Guo
Xiaoyan Zhang
Pingshan Li
Min Xu