Ian DeHaan

collaborators

2 papers

cs.DS2025

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson

Jungho Ahn, Ian DeHaan, Eun Jung Kim +1

We present a polynomial-time $(α_{G W} + ε)$ -approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $α_{G W} \approx 0.878$ is the a…

cs.DS2024

Approximate Minimum Sum Colorings and Maximum $k$ -Colorable Subgraphs of Chordal Graphs

Ian DeHaan, Zachary Friggstad

We give a $(1.796 + ε)$ -approximation for the minimum sum coloring problem on chordal graphs, improving over the previous 3.591-approximation by Gandhi et al. [2005]. To do so, we al…

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson

Approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs

Approximate Minimum Sum Colorings and Maximum $k$ -Colorable Subgraphs of Chordal Graphs