New Bounds for the Vertices of the Integer Hull

Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein


The vertices of the integer hull are the integral equivalent to the well-studied basic feasible solutions of linear programs. In this paper we give new bounds on the number of non-zero components -- their support -- of these vertices matching either the best known bounds or improving upon them. While the best known bounds make use of deep techniques, we only use basic results from probability theory to make use of the concentration of measure effect. To show the versatility of our techniques, we use our results to give the best known bounds on the number of such vertices and an algorithm to enumerate them. We also improve upon the known lower bounds to show that our results are nearly optimal. One of the main ingredients of our work is a generalization of the famous Hoeffding bound to vector-valued random variables that might be of general interest.
PublikationsstatusVeröffentlicht - 18.01.2020


Untersuchen Sie die Forschungsthemen von „New Bounds for the Vertices of the Integer Hull“. Zusammen bilden sie einen einzigartigen Fingerprint.