{"ID":6497760,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09222","arxiv_id":"2607.09222","title":"Polyhedral extended formulations that approximate the Gomory closure for packing problems","abstract":"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 $ε\u003e0$, the Lasserre hierarchy yields a polynomial-size convex but non-polyhedral extended formulation that approximates $P'$ up to a factor of $1+ε$. Our main result is the construction of a polyhedral and polynomial extended formulation that approximates $P'$ with the same approximation guarantee. Our construction is based on first principles. Like Mastrolilli's approach, ours also applies to higher iterates $P^{(t)}$ for fixed $t$ and $ε\u003e0$. In contrast to an explicit construction, communication complexity provides an alternative way to describe extended formulations. Using this approach we obtain a quasi-polynomial polyhedral extended formulation for the above problem that is superior in some parameter regimes. To achieve this, we describe a communication protocol extending Yannakakis' protocol to decide whether the clique of Alice and the stable set of Bob intersect.","short_abstract":"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 a...","url_abs":"https://arxiv.org/abs/2607.09222","url_pdf":"https://arxiv.org/pdf/2607.09222v1","authors":"[\"Friedrich Eisenbrand\",\"Samuel Fiorini\",\"Lars Rohwedder\",\"Jiaye Wei\"]","published":"2026-07-10T09:13:00Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}