Minimizing setup and beam-on times in radiation therapy

Nikhil Bansal, Don Coppersmith, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

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 "l"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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a
PublisherSpringer Verlag
Pages27-38
Number of pages12
ISBN (Print)3540380442, 9783540380443
DOIs
StatePublished - 2006
Externally publishedYes
Event9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 - Barcelona, Spain
Duration: Aug 28 2006Aug 30 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4110 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006
Country/TerritorySpain
CityBarcelona
Period8/28/068/30/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Minimizing setup and beam-on times in radiation therapy'. Together they form a unique fingerprint.

Cite this