APPLICATIONS OF CUT POLYHEDRA .1.

[摘要] In this paper and in its continuation (Part II, this issue), we group, within a unified framework, many applications of the following polyhedra: cut, boolean quadric, hypermetric and metric polyhedra. We treat, in particular, the following applications: l(1)- and L(1)-metrics in functional analysis, the max-cut problem, the Boole problem and multicommodity flow problems in combinatorial optimization, lattice holes in geometry of numbers, density matrices of many-fermions systems in quantum mechanics. We present some other applications, in probability theory, statistical data analysis and design theory. In this first part, after introducing the main definitions and operations for cut polyhedra, we describe the connections with l(1)-metrics and with other metric properties, and we consider, in particular, the applications to some classes of metrics arising from graphs, normed spaces and lattices.

[发布日期] 1994-11-21

[关键词] CUT;POLYHEDRON;VALID INEQUALITY;L(1)-METRIC;HYPERMETRIC;GRAPHIC METRIC;ULTRAMETRIC;ISOMETRIC EMBEDDING;CORRELATION OF EVENTS;MEASURE SPACE;LATTICE