ESA

We develop a framework that enables us to prove the conditional optimality of the shifting algorithms for several problems on unit ball graphs, such as maximum independent set, maximum induced forest, and many others, as well as for the problem of piercing unit balls.

Jun 26, 2026

We obtain fast algorithms for maximum coverage $k$-antichains and chains, and show the limits of the $\texttt{greedy}$ heuristic in these contexts.

Jun 26, 2026

We provide a $O(|\delta| \log |Q|)$-time algorithm computing a co-lex total preorder when the input is a Wheeler NFA, and an algorithm with the same time complexity computing the smallest-width co-lex partial order of any DFA.

Sep 4, 2023

We show that, for acyclic graphs, considering the width of the graph yields advances in our understanding of its approximability. For the non-negative version, we show that a popular heuristic is a $O( \log |X|)$-approximation on graphs satisfying two properties related to the width (satisfied by e.g., series-parallel graphs), and strengthen its worst-case approximation ratio for sparse graphs. For the negative version, we give a $(\lceil \log \Vert X \Vert \rceil +1)$-approximation using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary flows ($\Vert X \Vert \leq 1$) into at most width paths.

Sep 9, 2022