Preview

Chebyshevskii Sbornik

Advanced search

POLYHEDRAL STRUCTURES ASSOCIATED WITH QUASI-METRICS

https://doi.org/10.22405/2226-8383-2015-16-2-79-92

Abstract

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 l1-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 l1-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.

 

About the Authors

M. M. Deza
Ecole Normale Superieure
France
M. Dutour Sikiri´c (Zagreb, Croatia)


E. I. Deza
Московский педагогический государственный университет.
Russian Federation


M. Dutour Sikiri´c

Croatia


References

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. P. 51–60.

2. Deza M. M., Deza E. I. Encyclopedia of Distances / 3-rd edition. Berlin: SpringerVerlag, 2014. 716 p.

3. Deza M. M., Deza E. I. Cones of partial metrics // Contrib. Discrete Math. 2011. № 6(1). P. 26–47.

4. Deza M. M., Deza E. I., Vidali J. Cones of weighted and partial metrics // Proceedings of the International Conference on Algebra 2010. NJ: World Sci. Publ., 2012. P. 177– 197.

5. Deza M. M., Dutour Sikiri´c M. The hypermetric cone on 8 vertices and some generalizations // Preprint at arxiv:arXiv:1503.04554. 2013. Aviable at: http://arxiv.org/abs/ 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. 2002. Vol. 22. P. 199–225.

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. Sofia: ITHEA, 2012. Р. 31–53.

8. Deza M. M., Laurent M. Geometry of cuts and metrics. Berlin: Springer-Verlag, 1997. 517 c.

9. Deza M. M., Panteleeva E. I. Quasi-semi-metrics, oriented multi-cuts and related polyhedra // European Journal of Combinatorics. 2000. № 21(6). P. 777–795.

10. Fr´echet M. Sur quelques points du calcul fonctionnel // Rend. Circolo mat. Palermo. 1906. Vol. 22. PP. 1–74.

11. Hausdorff F. Grundz¨uge 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.

13. Matthews S. G. Partial metric topology (Papers on general topology and applications (Flushing, NY, 1992)) // Ann. New York Acad. Sci. 1994. Vol. 728. P. 183–197.

14. Seda A. K. Quasi-metrics and the semantic of logic programs // Fundamenta Informaticae. 1997. Vol. 9. P. 97–117.

15. Wilson W. A. On quasi-metric spaces // American J. of Math. 1931. Vol. 53. P. 575– 681.


Review

For citations:


Deza M.M., Deza E.I., Dutour Sikiri´c M. POLYHEDRAL STRUCTURES ASSOCIATED WITH QUASI-METRICS. Chebyshevskii Sbornik. 2015;16(2):79-92. (In Russ.) https://doi.org/10.22405/2226-8383-2015-16-2-79-92

Views: 500


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)