Faster optimal algorithms for segment minimization with small maximal value
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.
- Faster optimal algorithms for segment minimization with small maximal value
- Approximation algorithms for minimizing segments in radiation therapy
- A note on improving the performance of approximation algorithms for radiation therapy
- A network approach for segmentation in intensity modulated arc therapy
- Minimizing Setup and Beam-On Times in Radiation Therapy
- An integer linear programming formulation for the minimum cardinality segmentation problem
- Fast algorithms for minimum matrix norm with application in computer graphics
- A note on improving the performance of approximation algorithms for radiation therapy
- On explaining integer vectors by few homogeneous segments
- Faster optimal algorithms for segment minimization with small maximal value
This page was built for publication: Faster optimal algorithms for segment minimization with small maximal value
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1932452)
