Faster optimal algorithms for segment minimization with small maximal value (Q1932452)

Let \(A\) be an \(m\times n\) intensity matrix of non-negative integer values, whose entries represent the amount of radiation to be delivered through the corresponding bixel. In the special case where the largest value \(H\) in \(A\) small, the authors provide a fast exact algorithm for the single-row segmentation problem in \(O(p(H)Hn)\) time, which is polynomial in \(n\) as long as \(H\in O(\log{2n})\). Three important results are: (a) For general \(H\), a new algorithm yields an optimal solution to the full-matrix segmentation problem in \(O(mn^H/2^{(1-\epsilon)(H-1)})\) time for an arbitrarily small constant \(\epsilon>0\). (b) For \(H=2\), the full matrix problem with only entries in \(\{0,1,2\}\) can be solved optimally in \(O(mn)\) time. (c) For general \(H\), the new algorithm yields an optimal solution to the full-matrix lex-min problem in \(O(mn^H/2^{(1/2-\epsilon)(H-1)})\) time.