Geometry of Cuts and Metrics

Michel Marie Deza, Monique Laurent

588 pages, parution le 01/07/1999

Ajouter à une liste

Indisponible

Résumé

Cuts and metrics are well-known objects that arise - independently, but with many deep and fascinating connections - in diverse fields: in graph theory, combinatorial optimization, geometry of numbers, combinatorial matrix theory, statistical physics, VLSI design etc. This book offers a comprehensive summary together with a global view, establishing both old and new links.

Its treatment ranges from classical theorems of Menger and Schoenberg to recent developments such as approximation results for multicommodity flow and max-cut problems, metric aspects of Delaunay polytopes, isometric graph embeddings, and matrix completion problems. The discussion leads to many interesting subjects that cannot be found elsewhere, providing a unique and invaluable source for researchers and graduate students.

Contents

1 Outline of the Book 1
2 Basic Definitions 11

Part I : Measure Aspects : l[subscript 1]-Embeddability and Probability

3 Preliminaries on Distances 27
4 The Cut Cone and l[subscript 1]-Metrics 37
5 The Correlation Cone and {0,1}-Covariances 53
6 Conditions for L[subscript 1]-Embeddability 67
7 Operations 93
8 L[subscript 1]-Metrics from Lattices, Semigroups and Normed Spaces 105
9 Metric Transforms of L[subscript 1]-Spaces 113
10 Lipschitz Embeddings 125
11 Dimensionality Questions for l[subscript 1]-Embeddings 139
12 Examples of the Use of the L[subscript 1]-Metric 161

Part II : Hypermetric Spaces : an Approach via Geometry of Numbers

13 Preliminaries on Lattices 175
14 Hypermetrics and Delaunay Polytopes 193
15 Delaunay Polytopes: Rank and Hypermetric Faces 217
16 Extreme Delaunay Polytopes 235
17 Hypermetric Graphs 251

Part III : Isometric Embeddings of Graphs

18 Preliminaries on Graphs 279
19 Isometric Embeddings of Graphs into Hypercubes 283
20 Isometric Embeddings of Graphs into Cartesian Products 297
21 l[subscript 1]-Graphs 313

Part IV : Hypercube Embeddings and Designs

22 Rigidity of the Equidistant Metric 335
23 Hypercube Embeddings of the Equidistant Metric 341
24 Recognition of Hypercube Embeddable Metrics 353
25 Cut Lattices, Quasi h-Distances and Hilbert Bases 381

Part V : Facets of the Cut Cone and Polytope

26 Operations on Valid Inequalities and Facets 401
27 Triangle Inequalities 421
28 Hypermetric Inequalities 445
29 Clique-Web Inequalities 467
30 Other Valid Inequalities and Facets 487
31 Geometric Properties 511

Bibliography 551
Notation Index 575
Subject Index

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Michel Marie Deza, Monique Laurent
Parution	01/07/1999
Nb. de pages	588
Format	16 x 24
Couverture	Relié
Poids	995g
Intérieur	Noir et Blanc
EAN13	9783540616115