{"id":"hexagon/2610.00395","pdf":"https://hexagonmath.org/pdf/2610.00395v1","url":"https://hexagonmath.org/abs/2610.00395v1","tags":["math.CO","cs.DS","msc:90C27","msc:05C65","msc:05C70","msc:52B20","bin packing","configuration linear programming","hypergraph matching","lattice polytopes"],"score":0,"title":"Additive Rounding for LP-Tight Three-Item Bin Packing","domain":"math.OC","source":"hexagon","authors":["Ruixue Yuan","Da Teng","Zhenyu Sun"],"reviews":0,"subject":"math.OC","summary":"We consider bin-packing instances with \\(3m\\) items of sizes in \\((1/4,1/2)\\), total size \\(m\\), and configuration linear programming value \\(m\\). Let \\(d\\) be the relative dimension of the polytope of zero-sum multiplicity patterns obtained by centering sizes at \\(1/3\\). We determine the maximum additive integrality gap for every \\(d\\le10\\). It is zero for \\(d\\le4\\) and one for \\(5\\le d\\le10\\). More generally, a representation of the multiplicity vector by at most five zero-sum patterns admits an integral packing, and a representation by at most eleven patterns requires at most one…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-20","reactions":{},"withdrawn":false,"authorship":"human","formalized":false,"human_understanding":"all"}