research-article

Covering cubes and the closest vector problem

Authors:

Friedrich Eisenbrand,

Nicolai Hähnle,

Martin NiemeierAuthors Info & Claims

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Pages 417 - 423

https://doi.org/10.1145/1998196.1998264

Published: 13 June 2011 Publication History

Get Access

Abstract

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest lattice vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^(O(n)) (log(1/epsilon))^(O(n)) which improves upon the (2+1/epsilon)^(O(n)) running time of the previously best algorithm by Blömer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon>0, how many ellipsoids are necessary to cover the scaled unit cube [-1+epsilon, 1-epsilon]ⁿ such all ellipsoids are contained in the standard unit cube [-1,1]ⁿ. We provide an almost optimal bound for the case where the ellipsoids are restricted to be axis-parallel.

We then apply our covering scheme to a variation of this covering problem where one wants to cover the scaled cube with boxes that, if scaled by two, are still contained in the unit cube. Thereby, we obtain a method to boost any 2-approximation algorithm for closest-vector in the infinity-norm to a (1+epsilon)-approximation algorithm that has the desired running time.

References

[1]

M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pages 601--610 (electronic), New York, 2001. ACM.

Digital Library

Google Scholar

[2]

M. Ajtai, R. Kumar, and D. Sivakumar. Sampling short lattice vectors and the closest lattice vector problem. In Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on, 2002.

Digital Library

Google Scholar

[3]

S. Arora. Probabilistic checking of proofs and the hardness of approximation problems. PhD thesis, UC Berkeley, 1994.

Digital Library

Google Scholar

[4]

J. Blömer and S. Naewe. Sampling methods for shortest vectors, closest vectors and successive minima. Theoretical Computer Science, 410(18):1648--1665, 2009.

Digital Library

Google Scholar

[5]

I. Dinur, G. Kindler, R. Raz, and S. Safra. Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205--243, 2003.

Digital Library

Google Scholar

[6]

Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative algorithms for the shortest and closest lattice vector problems in any norm via M-ellipsoid coverings. Manuscript, 2010.

Google Scholar

[7]

P. Erdos and C. A. Rogers. Covering space with convex bodies. Acta Arith., 7:281--285, 1961/1962.

Crossref

Google Scholar

[8]

Z. Füredi and J.-H. Kang. Covering the n-space by convex bodies and its chromatic number. Discrete Math., 308(19):4495--4500, 2008.

Digital Library

Google Scholar

[9]

R. Kannan. Minkowski's convex body theorem and integer programming. Mathematics of Operations Research, 12(3):pp. 415--440, 1987.

Digital Library

Google Scholar

[10]

H. W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538 -- 548, 1983.

Digital Library

Google Scholar

[11]

D. Micciancio and P. Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Proceedings of the 42nd ACM symposium on Theory of computing, STOC '10, pages 351--358, New York, NY, USA, 2010. ACM.

Digital Library

Google Scholar

[12]

P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Mathematische Instituut, University of Amsterdam, 1981.

Google Scholar

Cited By

View all

Dadush DEisenbrand FRothvoss T(2024)From approximate to exact integer programmingMathematical Programming10.1007/s10107-024-02084-1Online publication date: 24-Apr-2024
https://doi.org/10.1007/s10107-024-02084-1
Gribanov DShumilov IMalyshev D(2023)Structured $$(\min ,+)$$-convolution and its applications for the shortest/closest vector and nonlinear knapsack problemsOptimization Letters10.1007/s11590-023-02017-518:1(73-103)Online publication date: 27-May-2023
https://doi.org/10.1007/s11590-023-02017-5
Dadush DEisenbrand FRothvoss T(2023)From Approximate to Exact Integer ProgrammingInteger Programming and Combinatorial Optimization10.1007/978-3-031-32726-1_8(100-114)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-32726-1_8
Show More Cited By

Index Terms

Covering cubes and the closest vector problem
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Covering Convex Bodies and the Closest Vector Problem
Abstract
We present algorithms for the $(1 + ϵ)$ -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 / ϵ)}^{n}$ . We improve this ... $_{}$ $^{}^{}$ $^{}^{}$ $_{}$ $^{}$ ${_{}}^{}$ $_{}$ $_{}$
An Improved Approximation Algorithm for the Most Points Covering Problem

In this paper we present a polynomial time approximation scheme for the most points covering problem. In the most points covering problem, n points in R ², r>0, and an integer m>0 are given and the goal is to cover the maximum number of points with m ...
Improved PTAS for the constrained k-means problem

The k-means problem has been paid lots of attention in many fields, and each cluster of the k-means problem always satisfies locality property. In this paper, we study the constrained k-means problem, where the clusters do not satisfy locality property ...

Comments

Information & Contributors

Information

Published In

SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

June 2011

532 pages

ISBN:9781450306829

DOI:10.1145/1998196

Program Chairs:
Ferran Hurtado
Universitat Politècnica de Catalunya
,
Marc van Kreveld
Utrecht University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '11

Sponsor:

SoCG '11: Symposium on Computational Geometry

June 13 - 15, 2011

Paris, France

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dadush DEisenbrand FRothvoss T(2024)From approximate to exact integer programmingMathematical Programming10.1007/s10107-024-02084-1Online publication date: 24-Apr-2024
https://doi.org/10.1007/s10107-024-02084-1
Gribanov DShumilov IMalyshev D(2023)Structured $$(\min ,+)$$-convolution and its applications for the shortest/closest vector and nonlinear knapsack problemsOptimization Letters10.1007/s11590-023-02017-518:1(73-103)Online publication date: 27-May-2023
https://doi.org/10.1007/s11590-023-02017-5
Dadush DEisenbrand FRothvoss T(2023)From Approximate to Exact Integer ProgrammingInteger Programming and Combinatorial Optimization10.1007/978-3-031-32726-1_8(100-114)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-32726-1_8
Eisenbrand FVenzin M(2022)Approximate CVP in time 20.802 Journal of Computer and System Sciences10.1016/j.jcss.2021.09.006124:C(129-139)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.jcss.2021.09.006
Naszódi MVenzin M(2022)Covering Convex Bodies and the Closest Vector ProblemDiscrete & Computational Geometry10.1007/s00454-022-00392-x67:4(1191-1210)Online publication date: 1-May-2022
https://doi.org/10.1007/s00454-022-00392-x
Rothvoss TVenzin M(2022)Approximate $$\mathrm {CVP}_{}$$ in Time $$2^{0.802 n}$$ - Now in Any Norm!Integer Programming and Combinatorial Optimization10.1007/978-3-031-06901-7_33(440-453)Online publication date: 27-May-2022
https://doi.org/10.1007/978-3-031-06901-7_33
Mukhopadhyay P(2021)Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in ℓp NormAlgorithms10.3390/a1412036214:12(362)Online publication date: 13-Dec-2021
https://doi.org/10.3390/a14120362
Mukhopadhyay P(2021)The Projection Games Conjecture and the Hardness of Approximation of super-SAT and related problemsJournal of Computer and System Sciences10.1016/j.jcss.2021.09.002Online publication date: Sep-2021
https://doi.org/10.1016/j.jcss.2021.09.002
Gribanov DMalyshev DPardalos PVeselov S(2018)FPT-algorithms for some problems related to integer programmingJournal of Combinatorial Optimization10.1007/s10878-018-0264-z35:4(1128-1146)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10878-018-0264-z
Gribanov D(2018)FPT Algorithms for the Shortest Lattice Vector and Integer Linear Programming ProblemsComputational Aspects and Applications in Large-Scale Networks10.1007/978-3-319-96247-4_2(19-35)Online publication date: 25-Aug-2018
https://doi.org/10.1007/978-3-319-96247-4_2
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Covering Convex Bodies and the Closest Vector Problem

An Improved Approximation Algorithm for the Most Points Covering Problem

Improved PTAS for the constrained k-means problem

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations