Radiation therapy is one of the commonly used cancer therapies. The radiation treatment poses a tuning problem: it needs to be effective enough to destroy the tumor, but it should maintain the functionality of the organs close to the tumor. Towards this goal the design of a radiation treatment has to be customized for each patient. Part of this design are intensity matrices that define the radiation dosage in a discretization of the beam head. To minimize the treatment time of a patient the beam-on time and the setup time need to be minimized. For a given row of the intensity matrix, the minimum beam-on time is equivalent to the minimum number of binary vectors with the consecutive “1”s property that sum to this row, and the minimum setup time is equivalent to the minimum number of distinct vectors in a set of binary vectors with the consecutive “1”s property that sum to this row. We give a simple linear time algorithm to compute the minimum beam-on time. We prove that the minimum setup time problem is APX-hard and give approximation algorithms for it using a duality property. For the general case, we give a 24/13 approximation algorithm. For unimodal rows, we give a 9/7 approximation algorithm. We also consider other variants for which better approximation ratios exist.

By:* Nikhil Bansal; Don Coppersmith; Baruch Schieber*

Published in: RC23945 in 2006

**LIMITED DISTRIBUTION NOTICE:**

**This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.**

Questions about this service can be mailed to reports@us.ibm.com .