Next: MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING Up: Mathematical Programming Previous: MAXIMUM CLASS-CONSTRAINED KNAPSACK Index

### NEAREST LATTICE VECTOR

- INSTANCE: Lattice basis where , a point , and a positive integer p.

- SOLUTION: A vector b in the lattice, where .

- MEASURE: The distance between b0 and b in the norm.

- Bad News: Not in APX [33].

- Comment: Not approximable within for any unless NPQP. The special case where b0 is the zero vector and is not approximable within for any unless NPQP [33].