Research

Research

Research Interests

My research interests include combinatorial optimization, integer programming and network analysis.

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 the 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 the 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). In 2004, Will Lindsey entered the graduate program at Purdue. Dan Steffy is in the Ph.D. program at Georgia Tech. 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 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 has accepted a job from the University of Detroit Mercy.