Quasi-semi-metrics, oriented multi-cuts and related polyhedra (Q1582485): Difference between revisions

The notion of quasi-metric \(d\) on a set \(X\) generalizes that of metric on \(X\) by dropping the symmetry condition \(d(x, y) = d(y, x)\) \(\forall x, y \in X\). A quasi-metric on \(\{ 1, 2, \dots , n \}\) can be regarded as a vector \((d_{i, j})_{i \neq j}\in \mathbb{R}^{n(n-1)}\) defined by \(d_{i, j} = d(i, j)\) and thus one can consider the cone and the polytope of all quasi-metrics on \(\{1,2,\dots , n \}\). An oriented multi-cut is a quasi-metric on \(\{ 1, 2, \dots , n \}\) associated with a partition \((S_1, S_2, \dots , S_q)\), \(q \geq 2\), of this set. It is defined by \(d(S_1, S_2, \dots , S_q)(a, b) = 1\) if \(a \in S_r\), \(b \in S_t\) and \(r < t\), and otherwise \(d(S_1, S_2, \dots , S_q)(a, b) = 0\). In this paper, the authors consider the cone and the polytope respectively of all quasi-metrics and of all multi-cuts on \(\{ 1, 2, \dots , n \}\), studying in detail the cases \(n =3, 4, 5\) and formulating several conjectures for general \(n\).