{"id":"arxiv/2607.09222","url":"https://arxiv.org/abs/2607.09222","tags":["math.OC"],"score":0,"title":"Polyhedral extended formulations that approximate the Gomory closure for packing problems","domain":"math.OC","source":"arxiv","authors":["Friedrich Eisenbrand","Samuel Fiorini","Lars Rohwedder","Jiaye Wei"],"reviews":0,"subject":"math.OC","summary":"We consider $0/1$ packing problems $\\max\\{c^T x \\colon Ax \\leq 1, \\, x \\in \\{0,1\\}^n\\}$, with $A \\in \\mathbb{R}_{\\geq 0}^{m \\times n}$. A way to solve such problems is via tightening the linear programming relaxation $P$ with Gomory \\emph{cutting-planes}. The Gomory-closure $P'$ of $P$ is the intersection of $P$ with all its cutting planes. The optimization problem over $P'$ is NP-hard. Mastrolilli (2020) has shown that for fixed $ε>0$, the Lasserre hierarchy yields a polynomial-size convex but non-polyhedral extended formulation that approximates $P'$ up to a factor of $1+ε$. Our main…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}