A quantitative Doignon-Bell-Scarf theorem

DOI10.1007/S00493-015-3266-9MaRDI QIDQ1743170zbMATH OpenOpenAlexFDO

Authors Robert Bassett, Quentin Louveaux, Iskander Aliev, Jesús A. De Loera

Publication date 12 April 2018

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2480, http://orca.cf.ac.uk/87665/1/DBS090316.pdf

zbMATH Keywords

Doignon-Bell-Scarf theorem

Mathematics Subject Classification ID

Helly-type theorems and geometric transversal theory (52A35) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10)

Abstract: The famous Doignon-Bell-Scarf Theorem is a Helly-type result about the existence of integer solutions on systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer $k$, we prove that there exists a constant $c(n,k)$, depending only on the dimension $n$ and $k$, such that if a polyhedron $x:Axleqb$ contains exactly k integer solutions, then there exists a subset of the rows, of cardinality no more than $c(n,k)$, defining a polyhedron that contains exactly the same $k$ integer points. In this case $c(n,0)=2^n$ is the original case of Doignon-Bell-Scarf for infeasible systems of inequalities. We work on both upper and lower bounds for the constant $c(n,k)$ and discuss some consequences, including a Clarkson-style algorithm to find the $l$-th best solution of an integer program with respect to the ordering induced by the objective function.

Recommendations

• Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• Transversal numbers over subsets of linear spaces
• Une borne optimale pour la programmation entière quasi-convexe
• scientific article; zbMATH DE number 4133835

Cites work

• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A Theorem Concerning the Integer Lattice
• An analysis of mixed integer linear sets based on lattice point free convex sets
• An observation on the structure of production sets with indivisibilities
• Bounds for Lattice Polytopes Containing a Fixed Number of Interior Points in a Sublattice
• Certificates of linear mixed integer infeasibility
• Constrained infinite group relaxations of MIPs
• Convexity in cristallographical lattices
• Equivalence between intersection cuts and the corner polyhedron
• Fast integer programming in fixed dimension
• Helly's Theorem with Volumes
• Helly-type theorems and generalized linear programming
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3626917 (Why is no real title available?)
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 1405493 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• Inequalities from Two Rows of a Simplex Tableau
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Lattice points in lattice polytopes
• Minimal valid inequalities for integer constraints
• Quantitative Helly-Type Theorems
• Violator spaces: Structure and algorithms

Cited in

(14)

• Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem
• Quantitative combinatorial geometry for concave functions
• Discrete quantitative Helly-type theorems with boxes
• A geometric approach to cut-generating functions
• Tight bounds on discrete quantitative Helly numbers
• Quantitative Tverberg theorems over lattices and other discrete sets
• Maximal S-free convex sets and the Helly number
• Helly’s theorem: New variations and applications
• Sublinear bounds for a quantitative Doignon-Bell-Scarf theorem
• A mélange of diameter Helly-type theorems
• Quantitative combinatorial geometry for continuous parameters
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Integer programs with prescribed number of solutions and a weighted version of Doignon-Bell-Scarf's theorem
• Midpoints of vertex pairs of convex polytopes

This page was built for publication: A quantitative Doignon-Bell-Scarf theorem

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