Practical colinear chaining on sequences revisited
We study the failing cases of $\texttt{Chainx}$, introduce the anchor diagonal distance, and find and implement an optimal algorithm working in $O(n\cdot OPT+n\log n)$ average-case time, where OPT $\le SOL$ is the optimal chaining cost.
Jun 8, 2025