Naslov
Polyhedral structures associated with quasi-metrics

Autori
Deza, Michel ; Deza, Irena ; Dutour Sikirić, Mathieu

Izvornik
Čebyševskij sbornik (2226-8383) 16 (2015), 2; 79-92

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Semi-metrics; cut and multicut; generalizations of cuts
(Semi-metrics; cut and multicut; generalization of cuts)

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA