A closest vector problem arising in radiation therapy planning

DOI10.1007/S10878-010-9308-8zbMATH Open1236.90104arXiv0907.0138OpenAlexW1793112875MaRDI QIDQ411241FDOQ411241

Authors: Céline Engelbeen, Samuel Fiorini, Antje Kiesel 

Publication date: 4 April 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: In this paper we consider the problem of finding a vector that can be written as a nonnegative integer linear combination of given 0-1 vectors, the generators, such that the l_1-distance between this vector and a given target vector is minimized. We prove that this closest vector problem is NP-hard to approximate within a O(d) additive error, where d is the dimension of the ambient vector space. We show that the problem can be approximated within a O(d^{3/2}) additive error in polynomial time, by rounding an optimal solution of a natural LP relaxation for the problem. We also observe that in the particular case where the target vector is integer and the generators form a totally unimodular matrix, the problem can be solved in polynomial time. The closest vector problem arises in the elaboration of radiation therapy plans. In this context, the target is a nonnegative integer matrix and the generators are certain 0-1 matrices whose rows satisfy the consecutive ones property. Here we mainly consider the version of the problem in which the set of generators comprises all those matrices that have on each nonzero row a number of ones that is at least a certain constant. This set of generators encodes the so-called minimum separation constraint.

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

Recommendations

• Minimizing Setup and Beam-On Times in Radiation Therapy
• Approximation algorithms for minimizing segments in radiation therapy
• On explaining integer vectors by few homogeneous segments
• CP and IP approaches to cancer radiotherapy delivery optimization
• On explaining integer vectors by few homogenous segments

zbMATH Keywords

closest vector problemradiation therapyconsecutive ones propertydecomposition of integer matricesminimum separation constraint

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• A threshold of ln n for approximating set cover
• Proof verification and the hardness of approximation problems
• Lattice-based Cryptography
• Tight results on minimum entropy set cover
• Decomposition of integer matrices and multileaf collimator sequencing
• A network flow algorithm to minimize beam‐on time for unconstrained multileaf collimator problems in cancer radiation therapy
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Approximating min sum set cover
• A duality based algorithm for multileaf collimator field segmentation with interleaf collision constraint
• Algorithms for sequencing multileaf collimators
• Randomized rounding in the presence of a cardinality constraint
• Reducing the tongue-and-groove underdosage in MLC shape matrix decomposition
• Constrained decompositions of integer matrices and their applications to intensity modulated radiation therapy
• Minimizing beam-on time in cancer radiation treatment using multileaf collimators
• Realization of Intensity Modulated Radiation Fields Using Multileaf Collimators

Cited In (5)

• GENERALIZED GEOMETRIC APPROACHES FOR LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY
• Approximation algorithms for minimizing segments in radiation therapy
• A function approximation approach to the segmentation step in IMRT planning
• On explaining integer vectors by few homogenous segments
• On explaining integer vectors by few homogeneous segments

This page was built for publication: A closest vector problem arising in radiation therapy planning

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