A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs

التفاصيل البيبلوغرافية
العنوان: A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
المؤلفون: Del Pia, Alberto, Khajavirad, Aida
سنة النشر: 2022
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Combinatorics, Mathematics - Optimization and Control, 90C09, 90C10, 90C26, 90C57
الوصف: We consider the multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs, hence characterizing the acyclic hypergraphs for which such a formulation can be constructed.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2212.11239
رقم الأكسشن: edsarx.2212.11239
قاعدة البيانات: arXiv