IBM Israel Research Seminars

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 intensity 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.

Joint work with Nikhil Bansal (IBM), Don Coppersmith (IDA).

About the Speaker
Baruch Schieber is the manager of the Optimization Center in the Mathematical Sciences Department in IBM T.J. Watson Research Center. In this capacity Baruch leads a group of Computer Scientists, Mathematicians and Operation Researchers in activities combining world class basic research with the design and implementation of state of the art software in areas such as supply chain management, personnel and vehicle scheduling, production planning, print technology and intrinsic function acceleration. Baruch received his PhD in Computer Science from Tel Aviv University in 1987 and joined IBM as a post doctoral fellow. His main interests are approximation algorithms, scheduling, and routing. Baruch has published more than 50 papers in scientific journals and is a regular presenter in leading Theoretical Computer Science conferences.