Configuration linear program: Difference between revisions

Revision as of 20:49, 9 February 2023

Revision as of 03:29, 13 February 2023

Line 47:

=== Rounding the fractional LP ===

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²(''n'')). Later, Hoberg and Rothvoss<ref name=":3">{{Citation|last1=Hoberg|first1=Rebecca|title=A Logarithmic Additive Integrality Gap for Bin Packing|date=2017-01-01|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.172|work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=2616–2625|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974782.172|isbn=978-1-61197-478-2|access-date=2021-02-10|last2=Rothvoss|first2=Thomas|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 ==