Naslov
Generalized cut and metric polytopes of graphs and simplicial complexes

Autori
Deza, Michel ; Dutour Sikirić, Mathieu

Izvornik
Optimization Letters (1862-4472) 14 (2020); 273-289

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

Ključne riječi
Metric polytope ; hemimetrics ; oriented metrics

Sažetak
The metric polytope METP(Kn) of the complete graph on n nodes is defined by the triangle inequalities x(i, j)≤x(i, k)+x(k, j) and x(i, j)+x(j, k)+x(k, i)≤2 for all triples i, j, k of {; ; ; 1, …, n}; ; ; . The cut polytope CUTP(Kn) is the convex hull of the {; ; ; 0, 1}; ; ; vectors of METP(Kn). For a graph G on n vertices the metric polytope METP(G) and cut polytope CUTP(G) are the projections of METP(Kn) and CUTP(Kn) on the edge set of G. The facets of the cut polytopes are of special importance in optimization and are studied here in some detail for many simple graphs. Then we define variants QMETP(G) for quasi-metrics, i.e. not necessarily symmetric distances and we give an explicit description by inequalities. Finally we generalize distances to m-dimensional area between m+1 points and this defines an hemimetric. In that setting the generalization of the notion of graph is the notion of m-dimensional simplicial complex K for which we define a cone of hemimetric HMET(K).

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA