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

DOI10.1007/S00493-020-4633-8MaRDI QIDQ2095112zbMATH OpenOpenAlexFDO

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

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 radiuslonely runner conjecturerational polytope

Mathematics Subject Classification ID

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

Review text

The authors consider the computational problem of determining the covering radius of a rational polytope. They propose a faster and simpler algorithm than this by \textit{R. Kannan} [Combinatorica 12, No. 2, 161--177 (1992; Zbl 0753.11013)]. It is applied for proving the following theorem being a special case of the well known Lonely Runner Conjecture stated by \textit{J. M. Wills} [Monatsh. Math. 72, 254--263, 368--381 (1968; Zbl 0188.10602)]: \par Theorem. Consider three runners with pairwise distinct constant velocities, who start running on a circular track of length \(11\), with not necessarily identical starting positions. A stationary spectator watches the runners from a fixed position along the track. Then, there exists a time at which all the runners have distance at least \(1/4\) from the spectator.

Recommendations

• On the Lonely Runner Conjecture.
• On the time for a runner to get lonely
• Six lonely runners
• Lonely runner polyhedra
• Some remarks on the lonely runner conjecture

Cites work

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

Cited in

(2)

• Computing the covering radius of a polytope with an application to lonely runners
• Linearly exponential checking is enough for the lonely runner conjecture and some of its variants

Describes a project that uses

Uses Software

• SageMath

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

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