## 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 language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a |

Publisher | Springer Verlag |

Pages | 27-38 |

Number of pages | 12 |

ISBN (Print) | 3540380442, 9783540380443 |

DOIs | |

State | Published - 2006 |

Externally published | Yes |

Event | 9th 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 2006 → Aug 30 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4110 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 |
---|---|

Country/Territory | Spain |

City | Barcelona |

Period | 8/28/06 → 8/30/06 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science