Mathieu Dutour Sikirić
Oriented Semi-metrics and Multicut Cones
Definitions
- Quasi-semi-metric Cone (QMETn): Defined by n(n-1)(n-2) oriented triangle inequalities (
xij + xjk - xik ≥ 0) and n(n-1) non-negativity inequalities (xij ≥ 0).
- Oriented Multi-cut Vector: For an oriented partition (S1, ..., Sq) of {1,...,n},
δij = 1 if i ∈ Sh and j ∈ Sk with h < k, and 0 otherwise.
- Oriented Multi-cut Cone (OMCUTn): The positive span of all oriented multi-cut vectors.
Computational Results
Cones for n=3, 4
| Cone | Dim | Group | Extreme Rays | Facets | Details |
|---|
| OMCUT3 = QMET3 | 6 | Sym(3) x Z2 | 12 (2 orbits) | 12 (2 orbits) | TeX | PS |
| OMCUT4 | 12 | Sym(4) x Z2 | 74 (5 orbits) | 72 (4 orbits) | TeX | PS |
| QMET4 | 12 | Sym(4) x Z2 | 164 (10 orbits) | 36 (2 orbits) | TeX | PS |
Cones for n=5
| Cone | Dim | Group | Extreme Rays | Facets | Details |
|---|
| OMCUT5 | 20 | Sym(5) x Z2 | 540 (9 orbits) | 35,320 (194 orbits) | — |
| QMET5 | 20 | Sym(5) x Z2 | 43,590 (229 orbits) | 80 (2 orbits) | TeX | PS |
| QHYP5 | 20 | Sym(5) x Z2 | 78,810 (386 orbits) | 90 (3 orbits) | TeX | PS |
Cones for n=6
| Cone | Dim | Group | Extreme Rays | Facets |
|---|
| OMCUT6 | 20 | Sym(6) x Z2 | 4,682 (19 orbits) | ≥ 217,847,040 (≥ 163,822 orbits) |
| QMET6 | 20 | Sym(6) x Z2 | ≥ 492,157,440 | 150 (2 orbits) |