Next:
MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING
Up:
Mathematical Programming
Previous:
MAXIMUM CLASS-CONSTRAINED KNAPSACK
 
Index
N
EAREST
L
ATTICE
V
ECTOR
I
NSTANCE:
Lattice basis
where
, a point
, and a positive integer
p
.
S
OLUTION:
A vector
b
in the lattice, where
.
M
EASURE:
The distance between
and
b
in the
norm.
Bad News:
Not in A
PX
[
35
].
Comment:
Not approximable within
for any
unless NP
QP. The special case where
is the zero vector and
is not approximable within
for any
unless NP
QP [
35
].
Viggo Kann
2000-03-20