Computing the covering radius of a polytope with an application to lonely runners

DOI10.1007/S00493-020-4633-8OpenAlexW3088842305MaRDI QIDQ2095112

Márton Naszódi, Jana Cslovjecsek, Matthias Schymura, Romanos-Diogenes Malikiosis

Publication date: 9 November 2022

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

algorithmcovering radiusrational polytopelonely runner conjecture

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Lattice packing and covering (number-theoretic aspects) (11H31) Diophantine inequalities (11J25)

Uses Software

• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the covering radius of lattice zonotopes and its relation to view-obstructions and the lonely runner conjecture
• Computing efficiently the lattice width in any dimension
• Inequalities for the lattice width of lattice-free convex sets in the plane
• Lifting properties of maximal lattice-free polyhedra
• Invisible runners in finite fields
• On the chromatic number of circulant graphs
• Covering minima and lattice-point-free convex bodies
• Lattice translates of a polytope and the Frobenius problem
• The lonely runner
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• The covering radius and a discrete surface area for non-hollow simplices
• Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
• Distances between optimal solutions of mixed-integer programs
• Zur simultanen homogenen diophantischen Approximation. I, II, III
• View-obstruction problems
• Integer Programming with a Fixed Number of Variables
• Some remarks on the lonely runner conjecture
• A Variable-Complexity Norm Maximization Problem
• Classification of empty lattice 4-simplices of width larger than two
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
• Lonely Runner Polyhedra
• On the Lattice Isomorphism Problem
• Six lonely runners

This page was built for publication: Computing the covering radius of a polytope with an application to lonely runners