A note on improving the performance of approximation algorithms for radiation therapy

DOI10.1016/J.IPL.2010.12.011zbMATH Open1260.68462DBLPjournals/ipl/BiedlDHLSY11arXiv0905.4930OpenAlexW2027206855WikidataQ59586051 ScholiaQ59586051MaRDI QIDQ1944893FDOQ1944893

Authors: Stephane Durocher, Holger H. Hoos, Shuang Luan, Jared Saia, Maxwell Young, Therese Biedl 

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: he segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes in each row are consecutive. This has direct applications in intensity-modulated radiation therapy, an effective form of cancer treatment. We develop three approximation algorithms for matrices with arbitrarily many rows. Our first two algorithms improve the approximation factor from the previous best of $1+lo{g}_{2}h$ to (roughly) $3/2cdot(1+lo{g}_{3}h)$ and $11/6cdot(1+lo{g}_{4}h)$, respectively, where $h$ is the largest entry in the intensity matrix. We illustrate the limitations of the specific approach used to obtain these two algorithms by proving a lower bound of $frac(2b-2)bcdotlo{g}_{b}h+frac1b$ on the approximation guarantee. Our third algorithm improves the approximation factor from $2cdot(logD+1)$ to $24/13cdot(logD+1)$, where $D$ is (roughly) the largest difference between consecutive elements of a row of the intensity matrix. Finally, experimentation with these algorithms shows that they perform well with respect to the optimum and outperform other approximation algorithms on 77% of the 122 test cases we consider, which include both real world and synthetic data.

Full work available at URL: https://arxiv.org/abs/0905.4930

Recommendations

• Approximation algorithms for minimizing segments in radiation therapy
• Faster optimal algorithms for segment minimization with small maximal value
• Faster optimal algorithms for segment minimization with small maximal value
• Discrete approximations to real-valued leaf sequencing problems in radiation therapy
• A network approach for segmentation in intensity modulated arc therapy

zbMATH Keywords

approximation algorithmsradiation therapy

Mathematics Subject Classification ID

Medical applications (general) (92C50) Approximation algorithms (68W25)

Cites Work

• The complexity of minimizing the number of shape matrices subject to minimal beam-on time in multileaf collimator field decomposition with bounded fluence
• Decomposition of integer matrices and multileaf collimator sequencing
• Optimal Multileaf Collimator Leaf Sequencing in IMRT Treatment Planning
• Hybrid methods for the multileaf collimator sequencing problem
• A network flow algorithm to minimize beam‐on time for unconstrained multileaf collimator problems in cancer radiation therapy
• Minimizing beam-on time in cancer radiation treatment using multileaf collimators
• Minimizing Setup and Beam-On Times in Radiation Therapy
• A new sequential extraction heuristic for optimizing the delivery of cancer radiation treatment using multileaf collimators
• Approximation algorithms for minimizing segments in radiation therapy

Cited In (6)

• Approximation algorithms for minimizing segments in radiation therapy
• Faster optimal algorithms for segment minimization with small maximal value
• Faster optimal algorithms for segment minimization with small maximal value
• Computing and Combinatorics
• On explaining integer vectors by few homogeneous segments
• Properties of an algorithm for solving the inverse problem in radiation therapy

This page was built for publication: A note on improving the performance of approximation algorithms for radiation therapy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944893)