Ian DeHaan

About Me

I am a PhD student in CSE at the University of Michigan, where I work with Euiwoong Lee on approximation algorithms. Before this, I worked on online algorithms with Kanstantsin Pashkovich at the University of Waterloo. Even earlier, I was a computing science undergrad at the University of Alberta, where I worked with Zachary Friggstad on approximation algorithms.

I'm primarily interested in approximation algorithms and structural graph theory. My research mostly involves looking at classical graph problems such as

• coloring problems,
• network design problems (e.g., TSP, orienteering),
• CSP-related problems (e.g., max-cut, SAT), and
• matching problems

on restricted graph classes such as

• interval graphs,
• chordal graphs,
• perfect graphs, and
• planar graphs.

Any interesting graph problem X paired with any interesting graph class Y results in the question of "how well can problem X be approximated on graph class Y?" Answering this question often involves discovering interesting things about the structure of graph class Y and how this structure interacts with problem X.
Besides graphs, I also take a side interest in matroids - it's certainly impossible to get a degree at UWaterloo without picking up such an interest.

Publications

• Matroid Bayesian Online Selection
  with Kanstantsin Pashkovich
  SAGT 2024
  arXiv proceedings
  
• Approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs
  with Zachary Friggstad
  WADS 2023
  arXiv proceedings
  

Competitive Programming

Everyone in CS should try competitive programming. Actually applying and implementing the ideas you learn in your algorithms classes leads to a far greater understanding than you would get just from seeing the proofs they work.

I used to compete in contests, qualifying for the ICPC world finals twice. But lately I've been more involved in coaching and problemsetting. I currently coach the talented programming teams at UMichigan and set problems for a wide array of local contests, many of which are available on open kattis.