J Michael Steele

Probability Theory and Combinatorial Optimization

• Broschiertes Buch

Produktbeschreibung

Provides an introduction to the state of the art of the probability theory that is most directly applicable to combinatorial optimization. Much attention is paid to those questions dealing with discrete optimization problems for points in Euclidean space, such as the minimum spanning tree, the travelling-salesman tour, and minimal-length matchings.

Produktdetails

• Verlag: Society for Industrial and Applied Mathematics (SIAM)
• Seitenzahl: 167
• Erscheinungstermin: 1. Januar 1987
• Englisch
• Abmessung: 253mm x 177mm x 10mm
• Gewicht: 308g
• ISBN-13: 9780898713800
• ISBN-10: 0898713803
• Artikelnr.: 23203470

Inhaltsangabe

1. Preface
2. Chapter 1: First View of Problems and Methods. A first example: Long common
subsequences
3. Subadditivity and expected values
4. Azuma’s inequality and a first application
5. A second example: The increasing-subsequence problem
6. Flipping Azuma’s inequality
7. Concentration on rates
8. Dynamic programming
9. Kingman’s subadditive ergodic theorem
10. Observations on subadditive subsequences
11. Additional notes
12. Chapter 2: Concentration of Measure and the Classical Theorems. The TSP and
quick application of Azuma’s inequality
13. Easy size bounds
14. Another mean Poissonization
15. The Beardwood-Halton-Hammersly theorem
16. Karp’s partitioning algorithms
17. Introduction to space-filling curve heuristic
18. Asymptotics for the space-filling curve heuristic
19. Additional notes
20. Chapter 3: More General Methods. Subadditive Euclidean functionals
21. Examples: Good, bad and forthcoming
22. A general L-(infinity) bound
23. Simple subadditivity and geometric subadditivity
24. A concentration inequality
25. Minimal matching
26. Two-sided bounds and first consequences
27. Rooted duals and their applications
28. Lower bounds and best possibilities
29. Additional remarks
30. Chapter 4: Probability in Greedy Algorithms and Linear Programming.
Assignment problem
31. Simplex method for theoreticians
32. Dyer-Frieze-McDiarmid inequality
33. Dealing with integral constraints
34. Distributional bounds
35. Back to the future
36. Additional remarks
37. Chapter 5: Distributional Techniques and the Objective Method. Motivation
for a method
38. Searching for a candidate object
39. Topology for nice sets
40. Information on the infinite tree
41. Dénoument
42. Central limit theory
43. Conditioning method for independence
44. Dependency graphs and the CLT
45. Additional remarks
46. Chapter 6: Talagrand’s Isoperimetric Theory. Talagrand’s isoperimetric
theory
47. Two geometric applications of the isoperimetric inequality
48. Application to the longest-increasing-subsequence problem
49. Proof of the isoperimetric problem
50. Application and comparison in the theory of hereditary sets
51. Suprema of linear functionals
52. Tail of the assignment problem
53. Further applications of Talagrand’s isoperimetric inequalities
54. Final considerations on related work
55. Bibliography
56. Index.