Atnaujinkite slapukų nuostatas

El. knyga: Geometry of Cuts and Metrics

  • Formatas: PDF+DRM
  • Serija: Algorithms and Combinatorics 15
  • Išleidimo metai: 12-Nov-2009
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • Kalba: eng
  • ISBN-13: 9783642042959
  • Formatas: PDF+DRM
  • Serija: Algorithms and Combinatorics 15
  • Išleidimo metai: 12-Nov-2009
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • Kalba: eng
  • ISBN-13: 9783642042959

DRM apribojimai

  • Kopijuoti:

    neleidžiama

  • Spausdinti:

    neleidžiama

  • El. knygos naudojimas:

    Skaitmeninių teisių valdymas (DRM)
    Leidykla pateikė šią knygą šifruota forma, o tai reiškia, kad norint ją atrakinti ir perskaityti reikia įdiegti nemokamą programinę įrangą. Norint skaityti šią el. knygą, turite susikurti Adobe ID . Daugiau informacijos  čia. El. knygą galima atsisiųsti į 6 įrenginius (vienas vartotojas su tuo pačiu Adobe ID).

    Reikalinga programinė įranga
    Norint skaityti šią el. knygą mobiliajame įrenginyje (telefone ar planšetiniame kompiuteryje), turite įdiegti šią nemokamą programėlę: PocketBook Reader (iOS / Android)

    Norint skaityti šią el. knygą asmeniniame arba „Mac“ kompiuteryje, Jums reikalinga  Adobe Digital Editions “ (tai nemokama programa, specialiai sukurta el. knygoms. Tai nėra tas pats, kas „Adobe Reader“, kurią tikriausiai jau turite savo kompiuteryje.)

    Negalite skaityti šios el. knygos naudodami „Amazon Kindle“.

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.

Cuts are well-known objects in graph theory, combinatorics, and combinatorial optimization and, perhaps less well-known, in analysis and probability theory. This book fascinates by its rigorous use of cut polyhedra to summarize various results in all these areas in a unified way, to point out unnoticed relations between diverse results in those fields, and to bring the existing links to light.

Recenzijos

From the reviews:



"This book is definitely a milestone in the literature of integer programming and combinatorial optimization. It draws from the Interdisciplinarity of these fields as it gathers methods and results from polytope theory, geometry of numbers, probability theory, design and graph theory around two objects, cuts and metrics. [ ] The book is very nicely written [ ] The book is also very well structured. With knowledge about the relevant terms, one can enjoy special subsections without being entirely familiar with the rest of the chapter. This makes it not only an interesting research book but even a dictionary. [ ] In my opinion, the book is a beautiful piece of work. The longer one works with it, the more beautiful it becomes." Robert Weismantel, Optima 56 (1997)





" In short, this is a very interesting book which is nice to have." Alexander I. Barvinok, MR 1460488 (98g:52001)









" This is a large and fascinating book. As befits a book which contains material relevant to so many areas of mathematics (and related disciplines such as statistics, physics, computing science, and economics), it is self-contained and written in a readable style. Moreover, the index, bibliography, and table of contents are all that they should be in such a work; it is easy to find as much or as little introductory material as needed." R.Dawson, Zentralblatt MATH Database 0885.52001



"This is a large and fascinating book. As befits a book which contains material relevant to so many areas of mathematics (and related disciplines such as statistics, physics, computing science, and economics), it is self-contained and written in a readable style. Moreover, the index, bibliography, and table of contents are all that they should be in such a work; it is easy to find as much or as little introductory material as needed." (R. Dawson, Zentralblatt MATH, 2001)

1. Outline of the Book
1(10)
1.1 Outline of Part I. Measure Aspects: XXX(1)-Embeddability and Probability
2(2)
1.2 Outline of Part II. Hypermetric Spaces: an Approach via Geometry of Numbers
4(2)
1.3 Outline of Part III. Embeddings of Graphs
6(1)
1.4 Outline of Part IV. Hypercube Embeddings and Designs
7(1)
1.5 Outline of Part V. Facets of the Cut Cone and Polytope
8(3)
2. Basic Definitions
11(12)
2.1 Graphs
11(3)
2.2 Polyhedra
14(4)
2.3 Algorithms and Complexity
18(1)
2.4 Matrices
19(4)
Part I. Measure Aspects: XXX(1)-Embeddability and Probability 23(144)
3. Preliminaries on Distances
27(10)
3.1 Distance Spaces and XXX(p)-Spaces
27(5)
3.2 Measure Spaces and L(p)-Spaces
32(5)
4. The Cut Cone and XXX(1)-Metrics
37(16)
4.1 The Cut Cone and Polytope
37(2)
4.2 XXX(1)-Spaces
39(4)
4.3 Realizations, Rigidity, Size and Scale
43(5)
4.4 Complexity Questions
48(3)
4.5 An Application to Statistical Physics
51(2)
5. The Correlation Cone and {0,1}-Covariances
53(14)
5.1 The Correlation Cone and Polytope
53(2)
5.2 The Covariance Mapping
55(3)
5.3 Covariances
58(3)
5.4 The Boole Problem
61(6)
6. Conditions for L(1)-Embeddability
67(26)
6.1 Hypermetric and Negative Type Conditions
67(6)
6.1.1 Hypermetric and Negative Type Inequalities
67(4)
6.1.2 Hypermetric and Negative Type Distance Spaces
71(1)
6.1.3 Analogues for Covariances
72(1)
6.2 Characterization of L(2)-Embeddability
73(9)
6.2.1 Schoenberg's Result and Cayley-Menger Determinants
74(4)
6.2.2 Menger's Result
78(2)
6.2.3 Further Characterizations
80(2)
6.3 A Chain of Implications
82(4)
6.4 An Example: The Spherical Distance Space
86(5)
6.5 An Example: Kalmanson Distances
91(2)
7. Operations
93(12)
7.1 The Gate Extension Operation
93(1)
7.2 The Antipodal Extension Operation
94(3)
7.3 The Spherical Extension Operation
97(1)
7.4 An Example: The Cocktail-Party Graph
98(3)
7.5 The Direct Product and Tensor Product Operations
101(2)
7.6 The 1-Sum Operation
103(2)
8. L(1)-Metrics from Lattices, Semigroups and Normed Spaces
105(8)
8.1 L(1)-Metrics from Lattices
105(2)
8.2 L(1)-Metrics from Semigroups
107(2)
8.3 L(1)-Metrics from Normed Spaces
109(4)
9. Metric Transforms of L(1)-Spaces
113(12)
9.1 The Schoenberg Transform
115(3)
9.2 The Biotope Transform
118(2)
9.3 The Power Transform
120(5)
10. Lipschitz Embeddings
125(14)
10.1 Embeddings with Distortion
125(5)
10.2 The Negative Type Condition for Lipschitz Embeddings
130(2)
10.3 An Application for Approximating Multicommodity Flows
132(7)
11. Dimensionality Questions for XXX(1)-Embeddings
139(22)
11.1 XXX(1)-Embeddings in Fixed Dimension
139(17)
11.1.1 The Order of Congruence of the XXX(1)-Space
141(4)
11.1.2 A Canonical Decomposition for Distances
145(3)
11.1.3 Embedding Distances in the XXX(1)-Plane
148(8)
11.2 On the Minimum XXX(p)-Dimension
156(5)
12. Examples of the Use of the L(1)-Metric
161(6)
12.1 The L(1)-Metric in Probability Theory
161(1)
12.2 The l(1)-Metric in Statistical Data Analysis
162(1)
12.3 The l(1)-Metric in Computer Vision and Pattern Recognition
163(4)
Part II. Hypermetric Spaces: an Approach via Geometry of Numbers 167(108)
13. Preliminaries on Lattices
175(18)
13.1 Distance Spaces
175(2)
13.2 Lattices and Delaunay Polytopes
177(12)
13.2.1 Lattices
177(2)
13.2.2 Delaunay Polytopes
179(3)
13.2.3 Basic Facts on Delaunay Polytopes
182(2)
13.2.4 Construction of Delaunay Polytopes
184(3)
13.2.5 Additional Notes
187(2)
13.3 Finiteness of the Number of Types of Delaunay Polytopes
189(4)
14. Hypermetrics and Delaunay Polytopes
193(24)
14.1 Connection between Hypermetrics and Delaunay Polytopes
193(6)
14.2 Polyhedrality of the Hypermetric Cone
199(7)
14.3 Delaunay Polytopes in Root Lattices
206(5)
14.4 On the Radius of Delaunay Polytopes
211(6)
15. Delaunay Polytopes: Rank and Hypermetric Faces
217(18)
15.1 Rank of a Delaunay Polytope
217(5)
15.2 Delaunay Polytopes Related to Faces
222(8)
15.2.1 Hypermetric Faces
222(4)
15.2.2 Hypermetric Facets
226(4)
15.3 Bounds on the Rank of Basic Delaunay Polytopes
230(5)
16. Extreme Delaunay Polytopes
235(16)
16.1 Extreme Delaunay Polytopes and Equiangular Sets of Lines
236(3)
16.2 The Schlafli and Gosset Polytopes are Extreme
239(5)
16.3 Extreme Delaunay Polytopes in the Leech Lattice XXX(24)
244(1)
16.4 Extreme Delaunay Polytopes in the Barnes-Wall Lattice XXX(16)
245(3)
16.5 Extreme Delaunay Polytopes and Perfect Lattices
248(3)
17. Hypermetric Graphs
251(24)
17.1 Characterizing Hypermetric and XXX(1)-Graphs
252(10)
17.2 Hypermetric Regular Graphs
262(7)
17.3 Extreme Hypermetric Graphs
269(6)
Part III. Isometric Embeddings of Graphs 275(56)
18. Preliminaries on Graphs
279(4)
19. Isometric Embeddings of Graphs into Hypercubes
283(14)
19.1 Djokovic's Characterization
283(3)
19.2 Further Characterizations
286(7)
19.3 Additional Notes
293(4)
20. Isometric Embeddings of Graphs into Cartesian Products
297(16)
20.1 Canonical Metric Representation of a Graph
297(8)
20.2 The Prime Factorization of a Graph
305(1)
20.3 Metric Decomposition of Bipartite Graphs
306(2)
20.4 Additional Notes
308(5)
21. l(1)-Graphs
313(18)
21.1 Results on l(1)-Graphs
313(3)
21.2 Construction of G via the Atom Graph
316(6)
21.3 Proofs
322(3)
21.4 More about l(1)-Graphs
325(6)
Part IV. Hypercube Embeddings and Designs 331(64)
22. Rigidity of the Equidistant Metric
335(6)
23. Hypercube Embeddings of the Equidistant Metric
341(12)
23.1 Preliminaries on Designs
341(9)
23.1.1 (r, XXX, n)-Designs and BIBD's
341(3)
23.1.2 Intersecting Systems
344(1)
23.2 Embeddings of 2t1(n) and Designs
345(2)
23.3 The Minimum h-Size of 2t1(n)
347(3)
23.4 All Hypercube Embeddings of 2t1(n) for Small n,t
350(3)
24. Recognition of Hypercube Embeddable Metrics
353(28)
24.1 Preliminary Results
354(3)
24.2 Generalized Bipartite Metrics
357(5)
24.3 Metrics with Few Values
362(8)
24.3.1 Distances with Values 2a, b (b odd)
363(2)
24.3.2 Distances with Values a,b,a+b (a,b odd)
365(2)
24.3.3 Distances with Values b,2a,b+2a (b odd, b less than 2a)
367(3)
24.4 Truncated Distances of Graphs
370(5)
24.4.1 The Class of Graphs H(k)
372(3)
24.5 Metrics with Restricted Extremal Graph
375(6)
25. Cut Lattices, Quasi h-Distances and Hilbert Bases
381(14)
25.1 Cut Lattices
381(4)
25.2 Quasi h-Distances
385(6)
25.3 Hilbert Bases of Cuts
391(4)
Part V. Facets of the Cut Cone and Polytope 395(156)
26. Operations on Valid Inequalities and Facets
401(20)
26.1 Cut and Correlation Vectors
401(2)
26.2 The Permutation Operation
403(1)
26.3 The Switching Operation
403(7)
26.3.1 Switching: A General Definition
403(2)
26.3.2 Switching: Cut Polytope versus Cut Cone
405(4)
26.3.3 The Symmetry Group of the Cut Polytope
409(1)
26.4 The Collapsing Operation
410(3)
26.5 The Lifting Operation
413(3)
26.6 Facets by Projection
416(5)
27. Triangle Inequalities
421(24)
27.1 Triangle Inequalities for the Correlation Polytope
423(1)
27.2 Rooted Triangle Inequalities
424(6)
27.2.1 An Integer Programming Formulation for Max-Cut
425(1)
27.2.2 Volume of the Rooted Semimetric Polytope
426(2)
27.2.3 Additional Notes
428(2)
27.3 Projecting the Triangle Inequalities
430(5)
27.3.1 The Semimetric Polytope of a Graph
431(3)
27.3.2 The Cut Polytope for Graphs with no K(5)-Minor
434(1)
27.4 An Excursion to Cycle Polytopes of Binary Matroids
435(10)
27.4.1 Preliminaries on Binary Matroids
436(2)
27.4.2 The Cycle Cone and the Cycle Polytope
438(3)
27.4.3 More about Cycle Spaces
441(4)
28. Hypermetric Inequalities
445(22)
28.1 Hypermetric Inequalities: Validity
445(2)
28.2 Hypermetric Facets
447(6)
28.3 Separation of Hypermetric Inequalities
453(4)
28.4 Gap Inequalities
457(6)
28.4.1 A Positive Semidefinite Relaxation for Max-Cut
459(4)
28.5 Additional Notes
463(4)
29. Clique-Web Inequalities
467(20)
29.1 Pure Clique-Web Inequalities
467(3)
29.2 General Clique-Web Inequalities
470(2)
29.3 Clique-Web Inequalities: Validity and Roots
472(5)
29.4 Clique-Web Facets
477(4)
29.5 Separation of Clique-Web Inequalities
481(2)
29.6 An Example of Proof for Clique-Web Facets
483(4)
30. Other Valid Inequalities and Facets
487(24)
30.1 Suspended-Tree Inequalities
487(5)
30.2 Path-Block-Cycle Inequalities
492(4)
30.3 Circulant Inequalities
496(1)
30.4 The Parachute Inequality
497(5)
30.4.1 Roots and Fibonacci Numbers
498(2)
30.4.2 Generalizing the Parachute Inequality
500(2)
30.5 Some Sporadic Examples
502(1)
30.6 Complete Description of CUT(n) and CUT(n) for nXXX7
503(3)
30.7 Additional Notes
506(5)
31. Geometric Properties
511(40)
31.1 Disproval of a Conjecture of Borsuk Using Cuts
512(2)
31.2 Inequalities for Angles of Vectors
514(1)
31.3 The Positive Semidefinite Completion Problem
515(12)
31.3.1 Results
516(6)
31.3.2 Characterizing Graphs with Excluded Induced Wheels
522(5)
31.4 The Euclidean Distance Matrix Completion Problem
527(7)
31.4.1 Results
529(2)
31.4.2 Links Between the Two Completion Problems
531(3)
31.5 Geometry of the Elliptope
534(5)
31.6 Adjacency Properties
539(7)
31.6.1 Low Dimension Faces
539(3)
31.6.2 Small Polytopes
542(4)
31.7 Distance of Facets to the Barycentrum
546(3)
31.8 Simplex Facets
549(2)
Bibliography 551(24)
Notation Index 575(4)
Subject Index 579