Minkowski’s convex body theorem and integer programming

Ravi Kannan

Mathematics of Operations Research 1987

Time bound

O(nⁿ s) arithmetic operations = n^n+o(n) poly(s)

Space bound

poly(s)

Source / version date

1987

Comparison variant

Provable · polynomial space

Cost scale

n^{c n + o(n)}

norm

Euclidean ℓ₂

Preprocessing cost

Included; arbitrary input basis

target

Arbitrary target

Computation model

Deterministic enumeration; bounded-bit arithmetic

success

Exact output

costScale

n log₂ n

Assumptions and source notes

Theorem 4.5 gives exact CVP in O(n^n s) arithmetic operations, where s is the input bit length. This establishes leading coefficient 1 on the n log n scale. The later n^{n/2+o(n)} CVP analysis is not backdated to Kannan.

Source location

§4, Theorem 4.5; polynomial bit-length bounds in the following paragraph
Version: Mathematics of Operations Research 12(3), 1987

Primary source ↗

@article{kannan-1987,
  author = {Ravi Kannan},
  title = {{Minkowski’s convex body theorem and integer programming}},
  journal = {Mathematics of Operations Research},
  year = {1987},
  month = {August},
  volume = {12},
  number = {3},
  pages = {415--440},
  doi = {10.1287/moor.12.3.415},
  url = {https://doi.org/10.1287/moor.12.3.415},
  cr_date = {1987-08-31},
  cr_date_precision = {month},
  cr_status = {published},
  cr_venue = {Mathematics of Operations Research},
  cr_author_ids = {ravi-kannan}
}