On the lattice programming gap of the group problems

DOI10.1016/J.ORL.2015.01.008MaRDI QIDQ1785637zbMATH OpenOpenAlexFDO

Authors Iskander Aliev

Publication date 1 October 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6967, http://orca.cf.ac.uk/75211/1/lattice_gap.pdf

zbMATH Keywords

covering radiusdiameters of graphsFrobenius numbersgroup relaxationsinteger programming gaplattices

Mathematics Subject Classification ID

The Frobenius problem (11D07) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: We show that computing the lattice programming gap of the group problems is NP-hard when the dimension is a part of input. We also obtain lower and upper bounds for the gap in terms of the cost vector and the determinant of the lattice.

Recommendations

• A sharp upper bound for the lattice programming gap
• On the unique shortest lattice vector problem
• scientific article; zbMATH DE number 4045845
• scientific article; zbMATH DE number 5506108
• Complexity of lattice problems. Non-approximability and limits of non-approximability

Cites work

• An optimal lower bound for the Frobenius problem
• Complexity of the Frobenius problem
• Computing the integer programming gap
• Cyclic group and knapsack facets
• Diameters of random circulant graphs
• Extensions of the Group Theoretic Approach in Integer Programming
• Feasibility of integer knapsacks
• Frobenius problem and the covering radius of a lattice
• Geometric algorithms and combinatorial optimization
• Gomory integer programs
• scientific article; zbMATH DE number 3987367 (Why is no real title available?)
• scientific article; zbMATH DE number 3664742 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3333393 (Why is no real title available?)
• Lattice translates of a polytope and the Frobenius problem
• Non-standard approaches to integer programming
• On the limit distribution of Frobenius numbers
• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• Some polyhedra related to combinatorial problems
• Sur la densité des réseaux de domaines convexes
• Testing additive integrality gaps
• The asymptotic distribution of Frobenius numbers
• The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
• The structure of group relaxations

Cited in

(3)

• Distances to lattice points in knapsack polyhedra
• A sharp upper bound for the lattice programming gap
• On densities of lattice arrangements intersecting every \(i\)-dimensional affine subspace

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On the lattice programming gap of the group problems

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