A closest vector problem arising in radiation therapy planning

Céline Engelbeen (), Samuel Fiorini () and Antje Kiesel ()
Additional contact information
Céline Engelbeen: Université Libre de Bruxelles
Samuel Fiorini: Université Libre de Bruxelles
Antje Kiesel: University of Rostock

Journal of Combinatorial Optimization, 2011, vol. 22, issue 4, No 10, 609-629

Abstract: 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.

Keywords: Closest vector problem; Decomposition of integer matrices; Consecutive ones property; Radiation therapy; Minimum separation constraint (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9308-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9308-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9308-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().