Polyhedral structures associated with quasi-metrics

M. M. Deza ; E. I. Deza ; M. Dutour Sikirić

Čebyševskij sbornik, Tome 16 (2015) no. 2, pp. 79-92.

Résumé

In this paper the problems of construction and description of cones and polyhedra of finite quasi-metrics are considered. These objects are asymmetrical analogs of classical finite metrics. The introduction presents the historical background and examples of applications of metrics and quasi-metrics. In particular, the questions connected with maximum cut problem are represented. In the first section definitions of finite metrics and semi-metrics are given, and also their major special cases are considered: cuts, muluticuts and hypersemimetrics. Cones and polyhedrons of the specified objects are constructed; their properties are investigated. Connections of the cut cone with metric $l_1$-spaces are indicated. The special attention is paid to symmetries of the constructed cones which consist of permutations and so-called switchings; transformation of a switching serves the basis for a choice of the inequalities defining the corresponding polyhedron. In the second section finite quasi-metrics and quasi-semimetrics are considered. They are asymmetrical analogs of the usual finite metrics and semimetrics. Definition of the oriented cuts and oriented multicuts are given: they are the most important special cases of the quasi-semimetrics. Concept of weightable quasi-metrics and related to them partial metrics is introduced. Cones and polyhedrons of these objects are constructed; their properties are investigated. Connections of the oriented cut cone with quasi-metric $l_1$-space are considered. The special attention is paid to symmetries of the constructed cones, which consist of permutations and oriented switchings; as well as in symmetric case, transformation of the oriented switching serves the basis for a choice of the inequalities defining the corresponding polyhedron. Different approaches to creation of a cone and a polyhedron of asymmetrical hypersemimetrics are considered. In the last section results of the calculations devoted to cones and to polyhedrons of quasi-semimetrics, the oriented cuts, the oriented multicuts, weighed quasimetrics and partial metrics for $3, 4, 5$ and $ 6$ points are considered. In fact, the dimension of an object, the number of its extreme rays (vertices) and their orbits, the number of its facets and their orbits, the diameters of the skeleton and the the ridge graph of the constructed cones and polyhedrons are specified. Bibliography: 15 titles.

Détail

Keywords: Semi-metrics, cut and multicut, hypersemimetric, cones and polyhedra of semimetrics, cuts and hypersemimetrics, quasi-semimetrics, oriented cut and multicut, weightable metric, partial metric, cones of quasi-semimetrics, of oriented cuts and oriented multicuts, of weightable and partial metrics, polyhedra of quasi-semimetrics, of oriented cuts and multicuts, of weightable and partial metrics.

Bibliographie

[1] Charikar M., Makarychev K., Makarychev V., “Directed metrics and directed graph partitioning problem”, Proc. of 11-th ACM-SIAM Symposium on Discrete Algorithms (2006), 51–60 | MR | Zbl

[2] Deza M. M., Deza E. I., Encyclopedia of Distances, 3-rd edition, Springer-Verlag, Berlin, 2014, 716 pp. | MR | Zbl

[3] Deza M. M., Deza E. I., “Cones of partial metrics”, Contrib. Discrete Math., 6:1 (2011), 26–47 | MR

[4] Deza M. M., Deza E. I., Vidali J., “Cones of weighted and partial metrics”, Proceedings of the International Conference on Algebra 2010, World Sci. Publ., NJ, 2012, 177–197 | MR | Zbl

[5] Deza M. M., Dutour Sikirić M., The hypermetric cone on 8 vertices and some generalizations, 2013, arXiv: 1503.04554

[6] Deza M. M., Dutour M., Panteleeva E. I., “Small cones of oriented semi-metrics”, Forum for Interdisciplinary Mathematics Proceedings on Statistics, Combinatorics Related Areas, Amer. J. Math. Management Sci., 22, 2002, 199–225 | MR | Zbl

[7] Deza M. M., Grishukhin V. P., Deza E. I., “Cones of weighted quasi-metrics, weighted quasi-hypermetrics and of oriented cuts”, Mathematics of Distances and Applications, ITHEA, Sofia, 2012, 31–53

[8] Deza M. M., Laurent M., Geometry of cuts and metrics, Springer-Verlag, Berlin, 1997, 517 pp. | MR | Zbl

[9] Deza M. M., Panteleeva E. I., “Quasi-semi-metrics, oriented multi-cuts and related polyhedra”, European Journal of Combinatorics, 21:6 (2000), 777–795 | DOI | MR | Zbl

[10] Fréchet M., “Sur quelques points du calcul fonctionnel”, Rend. Circolo mat. Palermo, 22 (1906), 1–74 | DOI | MR | Zbl

[11] Hausdorff F., Grundzüge der Mengenlehre, Leipzig, 1914

[12] Hitzler P., Generalized Metrics and Topology in Loic Programming Semantics, PhD Thesis, National University of Ireland: Univ. College Cork, 2001 | Zbl

[13] Matthews S. G., “Partial metric topology”, General topology and applications (Flushing, NY, 1992), Ann. New York Acad. Sci., 728, 1994, 183–197 | DOI | MR | Zbl

[14] Seda A. K., “Quasi-metrics and the semantic of logic programs”, Fundamenta Informaticae, 9 (1997), 97–117 | MR

[15] Wilson W. A., “On quasi-metric spaces”, American J. of Math., 53 (1931), 575–681 | MR