The difference between the optimal solution and the optimal integer solution of a linear program is called its integrality {\em gap}. Sometimes the difference between primal and dual integer optima is considered, or the difference between the integer optimum and the rounded linear optimum. We show some recent results on the gap for a selection of well-known and important, interrelated combinatorial problems :
First, for the so called Gilmore-Gomory linear formulation of the bin packing problem we consider a conjecture (of Scheithauer and Terno) stating that the gap is always at most 1. (Ongoing work with Gennady Shmonin.)
An important instance of the bin packing problem (constructed by Rizzi) will lead us to the {\em chromatic number of line graphs} , namely to the Goldberg-Seymour conjecture stating that the integrality gap of the related uniquely determined linear program is at most $1$.
More generally, for the chromatic number in arbitrary graphs, the gap of a most natural linear program is equal to the difference of the chromatic number and the clique number of the graph. The gap can be arbitrary large in this case and we determine its growth as a function of the number of vertices of the graph, exploring interesting interplays between Ramsey numbers and matchings (joint work with Andr\'as Gy\'arfas and Nicolas Trotignon, 2010).
Copyright. All Rights Reserved.