Generalizations Of Finite Metrics And Cuts

Elena Deza, Michel Deza;Mathieu Dutour Sikirić

• Publisher: WSPC
• Year: 2016
• ISBN:
  9789814740418
• Topic: Matematica
• Subtopic: Matematica discreta

This book introduces oriented version of metrics and cuts and their multidimensional analogues, as well as partial metrics and weighted metrics. It is a follow-up of Geometry of Cuts and Metrics by Deza and Laurent which presents rich theory of classical binary and symmetric objects — metrics and cuts.

Many research publications on this subject are devoted to different special aspects of the theory of generalized metrics. However, they are disconnected one from other, often written in different mathematical language, consider the same objects from different points of view without analysis of possible connections, etc. In this book we will construct full theory of main classes of finite generalized metrics and their polyhedral aspects.

Part V

Important cases of polyhedra of generalized finite semimetrics

Chapter 12

Cones of partial semimetrics and weightable quasi-semimetrics

12.1Preliminaries

For given two partial semimetrics p₁ and p₂ on a set X their non-negative linear combination d = αp₁ + βp₂, α, β ≥ 0, is a partial semimetric on X. Here, as usual, for all x, y ∈ X it holds

Similarly, for given two weightable quasi-semimetrics q₁ and q₂ on a set X their non-negative linear combination q = αq₁ + βq₂, α, β ≥ 0, is a weightable quasi-semimetric on X.

Then we can speak about the cones of all partial semimetrics and all weightable quasi-semimetrics on n points, in fact, on the set V_n = {1, 2, ..., n}. We can consider already the similar cones, related to cuts semimetrics, and some corresponding polytopes.

In this chapter we consider, for small values of n, the cone of all partial semimetrics on V_n (as well as the cones of weak and strong partial semimetrics on V_n), the cone of all weightable quasi-semimetrics on V_n (including weak and strong weightable quasisemimetrics on V_n), the cone of all weighted semimetrics on V_n (together with down-weighted and strong-weighted semimetrics on V_n). For any cone C under consideration we construct its {0, 1}-C cone, generated by all extreme rays of C, containing a non-zero {0, 1}-valued point. In some cases we try to construct similar polytopes.

Partial semimetrics are generalization of semimetrics, having important applications in Computer Science (Domain Theory, Analysis of Data Flow Deadlock, Complexity Analysis of Programs, etc.). They are used for treatment of partially defined/computed objects in Semantics of Computation.

Partial semimetrics were introduced by Matthews in [Matt92] for treatment of partially defined objects in Computer Science. Weak partial semimetrics were introduced in [Heck99] as a generalization of partial semimetrics, introduced in [Matt92]. ...