We present algorithms for the (1+epsilon)-approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of 2(O(n)) (1/epsilon)(n) . We improve th ...
We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time 2(0.802 n). This contrasts the corresponding 2(n) time, (gap)-SETH based lower bounds for these problems that even apply for ...
We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...
