Bin packing and unbounded configuration-LP gaps

The explanation

Take five items, each filling 0.4 of a bin. A bin holds a total of at most 1. Two items fit, using 0.8. Three do not, since they need 1.2. So the five items need three bins: two full pairs and one lone item. Packing items into as few bins as possible is called bin packing.

Now pretend bins could be shared out in fractions. Each bin carries a pair, so five items need two and a half bins. This pretend count has a name, the configuration LP (a linear program over bin patterns). List every way to fill one bin, called a pattern. Give each pattern a weight, which may be a fraction. Every item must be covered, and the total weight is kept as small as possible. The result never exceeds the true number of bins. Here it is 2.5, and rounding up gives exactly 3.

The idea goes back to cutting stock, with Gilmore and Gomory's method from 1961. People asked whether rounding up always gives the true answer. Odile Marcotte found an instance where it fails, in papers from 1985 and 1986. Guntram Scheithauer and Johannes Terno then studied a weaker bound. It allows one bin more than the rounded-up value. This is now called the Modified Integer Round-Up Conjecture. For the five items, it would allow up to four bins.

Fast methods show the same pattern. Here "fast" means a running time that grows like a fixed power of the input's length. Karmarkar and Karp in 1982 got within an extra amount growing like the square of the logarithm of the optimum. Hoberg and Rothvoss in 2017 cut this to an amount growing like the logarithm. Their method flips coins, and its bound is measured against the configuration LP. Williamson and Shmoys's 2011 textbook listed an open question. Can one fast method always stay within a fixed number of extra bins?

This paper answers both questions with no. Pick any whole number c, such as 1 or 100. It builds an instance whose configuration LP equals a whole number B exactly. Yet no packing fits into B plus c binsSource 1. Taking c equal to 1 breaks the conjectureSource 2. Every item is larger than 1/6, so no bin holds more than fiveSource 3. The LP value also stays B for a stricter LP whose patterns use each physical item copy at most onceSource 4.

The second result concerns fast methods. Fix any c. Telling instances that fit in B bins from those needing more than B plus c is NP-hardSource 5. NP-hard means a fast method for it would give fast methods for every problem in a large class called NP. So a fast method with a fixed allowance of extra bins exists exactly when P equals NPSource 6. Whether P equals NP is itself unproved.

The obstacle was that a real packing may use any pattern at all. Earlier constructions only blocked methods that round the patterns the LP happened to chooseSource 7. A true gap must defeat every possible packingSource 8. The paper encodes a network problem into item sizes near 1/5Source 9. The problem is vertex cover: choosing points in a network so that every link has at least one chosen end. Any packing into few bins can be read back as a small such choice. For the gap, the network is four points all joinedSource 10. Covering every link needs three points, but a tight packing would yield fewer. So no tight packing exists.

The gap comes at a price in size. The instances can grow very rapidly as c grows. The paper does not give a matching logarithmic lower bound in terms of instance sizeSource 11. So the logarithmic upper bounds above remain consistent with it. The gap result needs no unproved assumption, while the hardness result is about methods that do not flip coinsSource 12,Source 13.

How sure is this? A computer proof checker called Lean has checked formal versions of the main statements. They cover the gap for both LPs, the hardness for each c, and the link to P versus NP. The Lean statement is matched against a fixed reference statement by a tool called Comparator. No specialist review of the paper has been published.

What it doesn't show. This does not contradict the known methods that stay within a logarithmic number of extra bins.