Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
The paper establishes complexity of the well-known closest vector problem in an arbitrary norm in a lattice generated by a (0,1)-matrix --- the authors refer to this problem as (0,1)-CVP. In finite norms, this problem is NP-hard when the input vector contains nonzero elements. (0,1)-CVP in infinite norm is NP-hard if, and only if, the input vector contains at least one element with the absolute value bigger than 1. These results are applicable to problems on graphs and networks in which the corresponding incidence matrix generating the CVP lattice contains elements restricted to \(\{0,1\}\) or \(\{-1,0,1\}\). The authors used these result to establish complexity of data alignment in SIMD architectures. The presented complexity proofs use a reduction technique that can be useful in analyzing other minimization problems. The essence of this technique is to reduce a propositional logic problem to a satisfiability problem of an inequality over integers, which in turn is reduced to some minimization problem. The techniques generalize readily to complexity analysis of the related shortest vector problem (SVP) in infinity norm. SVP is NP-hard in infinity norm even if the lattice generating matrix contains elements restrited to \(\{0,1,r\}\), where \(| r|>1\). However, this problem has a (trivial) polynomial-time solution if the lattice generating matrix has all its elements in \(\{-1,0,1\}\). Recently, the authors extended the results of this paper as follows. Let \(A\) denote the matrix that generates the problem lattice, \(v\) stands for the input vector and \(r=gcd(A_{ij})\), \(s=\max\{| v_ i|\}\). In all norms CVP has a polynomial-time solution if \(s\leq| r|/2\), otherwise, it is NP-hard. For SVP in infinity norm, the problem is NP- hard if matrix \(A\) contains at least two nonzero elements with different absolute values. Otherwise, this problem has a polynomial-time solution.
- Approximating CVP to within almost-polynomial factors is NP-hard
- The Hardness of the Closest Vector Problem With Preprocessing Overell_inftyNorm
- The hardness of the closest vector problem with preprocessing
- scientific article; zbMATH DE number 1775383
- Sampling methods for shortest vectors, closest vectors and successive minima
- scientific article; zbMATH DE number 3516637 (Why is no real title available?)
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Minkowski's Convex Body Theorem and Integer Programming
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Reducibility among combinatorial problems
This page was built for publication: Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198041)
