Covering cubes and the closest vector problem

DOI10.1145/1998196.1998264zbMath1283.68358arXiv1012.2289OpenAlexW2030106244MaRDI QIDQ5404456

Nicolai Hähnle, Friedrich Eisenbrand, Martin Niemeier

Publication date: 24 March 2014

Published in: Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.2289

zbMATH Keywords

approximation algorithmcovering convex bodiesellipsoid coverbox coverclosest lattice vector problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (12)

Covering convex bodies and the closest vector problem ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ From approximate to exact integer programming ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ A randomized sieving algorithm for approximate integer programming ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ FPT-algorithms for some problems related to integer programming ⋮ Unnamed Item ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\)

This page was built for publication: Covering cubes and the closest vector problem