Abstract
In this paper we consider the following closest vector problem. We are given a set of 0–1 vectors, the generators, an integer vector, the target vector, and a nonnegative integer C. Among all vectors that can be written as nonnegative integer linear combinations of the generators, we seek a vector whose ℓ ∞-distance to the target vector does not exceed C, and whose ℓ 1-distance to the target vector is minimum.
First, we observe that the problem can be solved in polynomial time provided the generators form a totally unimodular matrix. Second, we prove that this problem is NP-hard to approximate within an O(d) additive error, where d denotes the dimension of the ambient vector space. Third, we obtain a polynomial time algorithm that either proves that the given instance has no feasible solution, or returns a vector whose ℓ ∞-distance to the target vector is within an \(O(\sqrt {d\ln d}\,)\) additive error of C and whose ℓ 1-distance to the target vector is within an \(O(d\sqrt{d\ln d}\,)\) additive error of the optimum. This is achieved by randomly rounding an optimal solution to a natural LP relaxation.
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 begin by considering 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. We conclude by giving further results on the approximability of the problem in the context of radiation therapy.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja RK, Hamacher HW (2005) A network flow algorithm to minimize beam-on time for unconstrained multileaf collimator problems in cancer radiation therapy. Networks 45:36–41
Alon N, Spencer J (1992) The probabilistic method. Wiley-Interscience series in discrete mathematics and optimization. Wiley-Interscience, New York
Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45(3):501–555
Baatar D, Hamacher HW, Ehrgott M, Woeginger GJ (2005) Decomposition of integer matrices and multileaf collimator sequencing. Discrete Appl Math 152:6–34
Bansal N (2010) Constructive algorithms for discrepancy minimization. arXiv:1002.2259v1
Boland N, Hamacher HW, Lenzen F (2004) Minimizing beam-on time in cancer radiation treatment using multileaf collimators. Networks 43(4):226–240
Bortfeld TR, Kahler DL, Waldron TJ, Boyer AL (1994) X-ray field compensation with multileaf collimators. Int J Radiat Oncol Biol Phys 28:723–730
Cardinal J, Fiorini S, Joret G (2008) Tight results on minimum entropy set cover. Algorithmica 51(1):49–60
Doerr B, Wahlström M (2009) Randomized rounding in the presence of a cardinality constraint. In: Proceedings of ALENEX 2009. SIAM, Philadelphia, pp 162–174
Engel K, Gauer T (2009) A dose optimization method for electron radiotherapy using randomized aperture beams. Phys Med Biol 54(17):5253–5270
Engelbeen C, Fiorini S (2009) Constrained decompositions of integer matrices and their applications to intensity modulated radiation therapy. Networks. doi:10.1002/net.20324
Feige U (1998) A threshold of ln n for approximating set cover. J ACM 45(4):634–652
Feige U, Lovász L, Tetali P (2004) Approximating min sum set cover. Algorithmica 40(4):219–234
Kalinowski T (2005) A duality based algorithm for multileaf collimator field segmentation with interleaf collision constraint. Discrete Appl Math 152:52–88
Kalinowski T (2006) Realization of intensity modulated radiation fields using multileaf collimators. In: Ahlswede R et al. (eds) Information transfer and combinatorics. LNCS, vol 4123. Springer, Berlin, pp 1010–1055
Kalinowski T (2008a) Multileaf collimator shape matrix decomposition. In: Lim GJ, Lee EK (eds) Optimization in medicine and biology. Auerbach Publishers, Boca Raton, pp 253–286
Kalinowski T (2008b) Reducing the tongue-and-groove underdosage in MLC shape matrix decomposition. Algorithmic Oper Res 3(2)
Kamath S, Sahni S, Li J, Palta J, Ranka S (2003) Leaf sequencing algorithms for segmented multileaf collimation. Phys Med Biol 48(3):307–324
Kamath S, Sahni S, Palta J, Ranka S, Li J (2004a) Optimal leaf sequencing with elimination of tongue-and-groove underdosage. Phys Med Biol 49:N7–N19
Kamath S, Sahni S, Ranka S, Li J, Palta J (2004b) A comparison of step-and-shoot leaf sequencing algorithms that eliminate tongue-and-groove effects. Phys Med Biol 49:3137–3143
Kiesel A, Gauer T (2009) Approximated segmentation considering technical and dosimetric constraints in intensity-modulated radiation therapy, submitted and part of the doctoral thesis “Implementierung der intensitätsmodulierten Strahlentherapie mit Elektronen” of Tobias Gauer, Department of Radiotherapy and Radio-Oncology, University Medical Center Hamburg-Eppendorf
Micciancio D, Regev O (2008) Lattice-based cryptography. In: Bernstein DJ, Buchmann J (eds) Post-quantum cryptography. Springer, Berlin
Motwani R, Naor J, Raghavan P (1997) Randomized approximation algorithms in combinatorial optimization. In: Hochbaum D (ed) Approximation algorithms for NP-hard problems. PWS, Boston, pp 447–481
Que W, Kung J, Dai J (2004) ‘Tongue-and-groove’ effect in intensity modulated radiotherapy with static multileaf collimator fields. Phys Med Biol 49:399–405
Raghavan P (1988) Probabilistic construction of deterministic algorithms: approximating packing integer programs. J Comput Syst Sci 37:130–143
Srinivasan A (2001) Distributions on level-sets with applications to approximation algorithms. In: 42nd IEEE symposium on foundations of computer science, Las Vegas, NV, 2001. IEEE Comput. Soc., Los Alamitos, pp 588–597
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by an “Actions de Recherche Concertées” (ARC) project of the “Communauté française de Belgique”. Céline Engelbeen is a research fellow of the “Fonds pour la Formation à la Recherche dans l’Industrie et dans l’Agriculture” (FRIA) and Antje Kiesel is a research fellow of the German National Academic Foundation.
Rights and permissions
About this article
Cite this article
Engelbeen, C., Fiorini, S. & Kiesel, A. A closest vector problem arising in radiation therapy planning. J Comb Optim 22, 609–629 (2011). https://doi.org/10.1007/s10878-010-9308-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-010-9308-8