Facet classification conjecture for the oriented-multicut cone
Facet classification conjecture for the oriented-multicut cone
Let be the cone of oriented multicuts. A zero-extension of an inequality on is the inequality obtained by adding a zero coordinate for the new element. Let denote a hypermetric inequality, and let and be the inequalities defined in the paper.
Oriented-multicut facet conjecture. The following inequalities define facets of : (i) zero-extensions of every facet of , including oriented triangle and non-negativity inequalities; (ii) every hypermetric inequality except non-oriented triangle inequalities; and (iii) the inequalities and .
The conjecture was checked by computer for . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.