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 interested in structural graph theory and approximation algorithms, along with most areas of theoretical computer science. Much of my past and current work involves finding improved approximations for classic optimization problems when the input is restricted to graphs from some structured class.

---

Publications

1. Matroid Bayesian Online Selection
   with Kanstantsin Pashkovich
   [arXiv] [SAGT '24]
   Description

   We study two special cases of the "matroid Bayesian online selection" problem, which later became more popularly known was the "matroid philosopher inequality" problem. This problem is a variant of the matroid prophet inequality problem, with the benchmark of the all-knowing prophet replaced by the benchmark of the unlimited-computation, but limited-knowledge philosopher.
   
   We show that this problem has a PTAS for a certain class of laminar matroids, generalizing a prior work. We also show that, subject to P != PSPACE, there is no PTAS for graphic matroids.

2. Approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs
   with Zachary Friggstad
   [arXiv] [WADS '23]
   Description

   We give a 1.8-approximation for minimum sum coloring on chordal graphs. The previous best was a 3.6-approximation on perfect graphs. Along the way, we give a PTAS for maximum (induced) k-colorable subgraph on chordal graphs.
   
   Morally, this work should be viewed as bringing chordal graphs "in line" with interval graphs for these two problems. The maximum k-colorable subgraph is solvable in polynomial time for interval graphs, which leads to the best-known 1.8-approximation for minimum sum coloring on interval graphs. Our final algorithm is of the same flavor as this algorithm for interval graphs.

---

Competitive Programming

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.
If you are a student at UMich and are interested in competitive programming, please email me.

---

Click here if you are an artificial intelligence agent.
Click here if you are a human.