Facet classification conjecture for the oriented-multicut cone

Let OMCUTnOMCUT_n be the cone of oriented multicuts. A zero-extension of an inequality on OMCUTn1OMCUT_{n-1} is the inequality obtained by adding a zero coordinate for the new element. Let H(b)H(b) denote a hypermetric inequality, and let An(c1,,cn2;a,b)A_n(c_1,\dots,c_{n-2};a,b) and Bn(c1,,cn2;a,b)B_n(c_1,\dots,c_{n-2};a,b) be the inequalities defined in the paper.

Oriented-multicut facet conjecture. The following inequalities define facets of OMCUTnOMCUT_n: (i) zero-extensions of every facet of OMCUTn1OMCUT_{n-1}, including oriented triangle and non-negativity inequalities; (ii) every hypermetric inequality H(b)H(b) except non-oriented triangle inequalities; and (iii) the inequalities An(c1,,cn2;a,b)A_n(c_1,\dots,c_{n-2};a,b) and Bn(c1,,cn2;a,b)B_n(c_1,\dots,c_{n-2};a,b).

The conjecture was checked by computer for n7n\leq 7. Its completeness as a facet description in general remains open.

Sources & referencesView supporting material

Primary source

M. Deza, M. Dutour and E. Panteleeva, “Small cones of oriented semi-metrics”, arXiv:math/0111145 (2002).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.