Can I read Metric extensions and the L1 hierarchy on EtoBox?

Metric extensions and the L1 hierarchy by David Avis; Hiroshi Maehara is a Computer Science article available to read on EtoBox.

What is Metric extensions and the L1 hierarchy about?

A finite semimetric is L'-embeddable if it can be expressed as a non-negative combination of Hamming semimetrics. A finite semimetric is called hypermetric if it satisfies the (2k + 1)-gonad inequalities which naturally generalize the triangle inequality. It is known that all L'-embeddable semimetrics are hypermetric and the metric induced by K7 -P, is hypermetric but not L'-embeddable. In the first part of the paper we show that there are infinite metrics that are hypermetric but are not L'-embeddable, answering a question of Deza. We introduce the r-extension of a semimetric: this is the addition of new points from which all of the distances are r. We show that all 2-extensions of K, -P3 are hypermetric. Unfortunately, ## 2-extensions of hypermetrics in which all of the distances are either one or two may not be hypermetric in general. We illustrate this by showing that the metric induced by the star K,,, (which is hypermetric) has a nonhypermetric 2-extension involving three additional points. In the second part of the paper, we show that l-extensions of the metric induced by Kq-P3 form a family that span a hierarchy of metrics that contain L'. A finite semimetric is of negative

Who reads Metric extensions and the L1 hierarchy?

Author

David Avis; Hiroshi Maehara

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)

Published

1994

Language

EN

Field

Computer Science (Physical Sciences)