Reference : A Quantitative Doignon-Bell-Scarf theorem |

Scientific journals : Article | |||

Physical, chemical, mathematical & earth Sciences : Mathematics | |||

http://hdl.handle.net/2268/187395 | |||

A Quantitative Doignon-Bell-Scarf theorem | |

English | |

Aliev, Iskander [Cardiff University > Mathematics Department > > >] | |

Bassett, Robert [University of California, Davis - UC Davis > Department of Mathematics > > >] | |

De Loera, Jesus [University of California, Davis - UC Davis > Department of Mathematics > > >] | |

Louveaux, Quentin [Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >] | |

In press | |

Combinatorica | |

Springer Science & Business Media B.V. | |

Yes (verified by ORBi) | |

International | |

0209-9683 | |

1439-6912 | |

[en] Lattice points ; Polyhedra | |

[en] The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions to 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 on the number k, such that if a bounded polyhedron {x in R^n : Ax <= b} contains exactly k integer points, 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 as in 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. | |

Researchers | |

http://hdl.handle.net/2268/187395 | |

10.1007/s00493-015-3266-9 |

File(s) associated to this reference | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.