Cones of partial metrics

  • Michel Deza
  • Elena Deza

Abstract

A partial semimetric on a set X is a function $(x, y) \mapsto p(x, y) \in \RR_{\geq 0}$ satisfying $p(x, y) = p(y, x)$, $p(x, y) \geq p(x, x)$ and $p(x, z) \leq p(x, y) + p(y, z) − p(y, y)$ for all $x, y, z \in X$. We study here the polyhedral convex cone $PSMET_n$ of all partial semimetrics on $n$ points, using computations done for $n \leq 6$. We present data on those cones and their relatives: the number of facets, of extreme rays, of their orbits, incidences, characterize ${0, 1}$- valued extreme rays, etc.
Published
2011-04-04
Section
Articles