تقرير
Steiner Cut Dominants
العنوان: | Steiner Cut Dominants |
---|---|
المؤلفون: | Conforti, Michele, Kaibel, Volker |
سنة النشر: | 2022 |
المجموعة: | Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics, Mathematics - Optimization and Control, 90C57, 90C27, 65K05 |
الوصف: | For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut \delta(S) where S intersects both T and the complement of T. The T-Steiner cut dominant} of G is the dominant CUT_+(G,T) of the convex hull of the incidence vectors of the T-Steiner cuts of G. For T={s,t}, this is the well-understood s-t-cut dominant. Choosing T as the set of all nodes of G, we obtain the \emph{cut dominant}, for which an outer description in the space of the original variables is still not known. We prove that, for each integer \tau, there is a finite set of inequalities such that for every pair (G,T) with |T|\ <= \tau the non-trivial facet-defining inequalities of CUT_+(G,T) are the inequalities that can be obtained via iterated applications of two simple operations, starting from that set. In particular, the absolute values of the coefficients and of the right-hand-sides in a description of CUT_+(G,T) by integral inequalities can be bounded from above by a function of |T|. For all |T| <= 5 we provide descriptions of CUT_+(G,T) by facet defining inequalities, extending the known descriptions of s-t-cut dominants. Comment: 24 pages, 20 figures; to appear in Math. of Operations Research |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2209.14802 |
رقم الأكسشن: | edsarx.2209.14802 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |