Karmarkar and Karp further developed a way to round the fractional LP into an approximate solution to the integral LP; see [[Karmarkar-Karp bin packing algorithms]]. Their proof shows that the additive [[integrality gap]] of this LP is in O(log<sup>2</sup>(''n'')). Later, Hoberg and Rothvoss<ref name=":3">{{Citationcite book|last1=Hoberg|first1=Rebecca |titledoi=A Logarithmic Additive Integrality Gap for Bin Packing10.1137/1.9781611974782.172|dateisbn=2017978-011-0161197-478-2|worklast2=Rothvoss|first2=Thomas|title=Proceedings of the 2017Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms |pageschapter=2616–2625|series=ProceedingsA Logarithmic Additive Integrality Gap for Bin Packing |publisher=Society for Industrial and Applied Mathematics |doidate=10.1137/1.9781611974782.1722017 |isbnpages=978-1-61197-478-2|last2=Rothvoss|first2=Thomas2616–2625 |s2cid=1647463|doi-access=free}}</ref> improved their result and proved that the integrality gap is in O(log(''n'')). The best known lower bound on the integrality gap is a constant Ω(1). Finding the exact integrality gap is an open problem.
== In bin covering ==
In the [[bin packing|bin covering problem]], there are ''n'' items with different sizes. The goal is to pack the items into a ''maximum'' number of bins, where each bin should contain ''at least'' ''B''. A natural configuration LP for this problem could be:<blockquote><math>\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\leq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math></blockquote>where '''''A''''' represents all configurations of items with sum ''at least'' ''B'' (one can take only the inclusion-minimal configurations). The problem with this LP is that, in the bin-covering problem, handling small items is problematic, since small items may be essential for the optimal solution. With small items allowed, the number of configurations may be too large even for the technique of Karmarkar and Karp. Csirik, Johnson and Kenyon<ref name=":24">{{Cite journalbook|last1=Csirik|first1=Janos|last2=Johnson|first2=David S.|last3=Kenyon|first3=Claire|date=2001-01-09|titlechapter=Better approximation algorithms for bin covering |date=2001-01-09 |chapter-url=https://dl.acm.org/doi/abs/10.5555/365411.365533 |journaltitle=SODA '01: Proceedings of the Twelfthtwelfth Annualannual ACM-SIAM Symposiumsymposium on Discrete Algorithms|series=SODA '01|___location=Washington, D.C.,algorithms USA|publisher=Society for Industrial and Applied Mathematics |pages=557–566|isbn=978-0-89871-490-6}}</ref> present an alternative LP. First, they define a set of items that are called ''small''. Let ''T'' be the total size of all small items. Then, they construct a matrix '''A''' representing all configurations with sum < 2. Then, they consider the above LP with one additional constraint:<math display="block">\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~\text{s.t.}</math><math display="block">A \mathbf{x}\leq \mathbf{n}</math><math display="block">\sum_{c\in C: sum(c)<B} (B-sum(c))\cdot x_c \leq T</math><math display="block">\mathbf{x}\geq 0</math>The additional constraint guarantees that the "vacant space" in the bins can be filled by the small items. The dual of this LP is more complex and cannot be solved by a simple knapsack-problem separation oracle. Csirik, Johnson and Kenyon<ref name=":24" /> present a different method to solve it approximately in time exponential in 1/epsilon. Jansen and Solis-Oba'''<ref name=":32">{{Cite journalbook|last1=Jansen|first1=Klaus|last2=Solis-Oba|first2=Roberto|datetitle=2002-11-21Algorithms and Computation |titlechapter=An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering |series=Lecture Notes in Computer Science |date=2002-11-21 |volume=2518 |url=https://dl.acm.org/doi/abs/10.5555/646345.689912|journal=Proceedingsof the 13th International Symposium on Algorithms and Computation|series=ISAAC '02|volume=2518|___location=Berlin, Heidelberg|publisher=Springer-Verlag |pages=175–186|doi=10.1007/3-540-36136-7_16|isbn=978-3-540-00142-3}}</ref>''' present an improved method to solve it approximately in time exponential in 1/epsilon.
