Computing efficiently the lattice width in any dimension

DOI10.1016/J.TCS.2011.02.009MaRDI QIDQ638564zbMATH OpenOpenAlexFDO

Authors Émilie Charrier, Fabien Feschet, Lilian Buzer

Publication date 12 September 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://hal-upec-upem.archives-ouvertes.fr/hal-00827179/file/article_TCS.pdf

zbMATH Keywords

greedy algorithmlattice widthshortest vector

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Integer programming (90C10)

Recommendations

• Efficient lattice width computation in arbitrary dimension
• Efficient algorithms for discrete lattice calculations
• Lattice computers for approximating Euclidean space
• Computing the writhe on lattices
• Computing a lattice basis revisited
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Fast lattice point enumeration with minimal overhead
• Computing rank-width exactly
• An Efficient Data Structure for Lattice Operations
• Rigorous and Efficient Short Lattice Vectors Enumeration

Cites work

• scientific article; zbMATH DE number 3848644 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1121921 (Why is no real title available?)
• scientific article; zbMATH DE number 1121922 (Why is no real title available?)
• scientific article; zbMATH DE number 1757949 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• scientific article; zbMATH DE number 1436417 (Why is no real title available?)
• A Polynomial Algorithm for the Two-Variable Integer Programming Problem
• A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
• A linear algorithm for integer programming in the plane
• Computing Two-Dimensional Integer Hulls
• Computing the width of a set
• Efficient lattice width computation in arbitrary dimension
• Finding Extremal Polygons
• Finding a shortest vector in a two-dimensional lattice modulo m
• Higher dimensional continued fractions
• Integer Programming with a Fixed Number of Variables
• Minimal ellipsoids and maximal simplexes in 3D Euclidean space
• On integer points in polyhedra
• Production Sets with Indivisibilities, Part I: Generalities
• Sieve algorithms for the shortest vector problem are practical
• Simultaneous inner and outer approximation of shapes
• The Generalized Gauss Reduction Algorithm

Cited in

(5)

• Lattice size and generalized basis reduction in dimension three
• Computing rank-width exactly
• Efficient lattice width computation in arbitrary dimension
• On factorization invariants and Hilbert functions
• Computing the covering radius of a polytope with an application to lonely runners

This page was built for publication: Computing efficiently the lattice width in any dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638564)