Skip to content
Register Sign in Wishlist
Probability Theory and Combinatorial Optimization

Probability Theory and Combinatorial Optimization


Part of CBMS-NSF Regional Conference Series in Applied Mathematics

  • Date Published: December 1997
  • availability: Available in limited markets only
  • format: Paperback
  • isbn: 9780898713800

£ 36.99

Available in limited markets only
Unavailable Add to wishlist

Looking for an inspection copy?

This title is not currently available on inspection

Product filter button
About the Authors
  • This monograph provides an introduction to the state of the art of the probability theory that is most directly applicable to combinatorial optimization. The questions that receive the most attention are those that deal with discrete optimization problems for points in Euclidean space, such as the minimum spanning tree, the traveling-salesman tour, and minimal-length matchings. Still, there are several nongeometric optimization problems that receive full treatment, and these include the problems of the longest common subsequence and the longest increasing subsequence. The philosophy that guides the exposition is that analysis of concrete problems is the most effective way to explain even the most general methods or abstract principles.

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity


    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?


    Product details

    • Date Published: December 1997
    • format: Paperback
    • isbn: 9780898713800
    • length: 167 pages
    • dimensions: 250 x 177 x 9 mm
    • weight: 0.304kg
    • availability: Available in limited markets only
  • Table of Contents

    1. First View of Problems and Methods. A first example. Long common subsequences
    Subadditivity and expected values
    Azuma's inequality and a first application
    A second example. The increasing-subsequence problem
    Flipping Azuma's inequality
    Concentration on rates
    Dynamic programming
    Kingman's subadditive ergodic theorem
    Observations on subadditive subsequences
    Additional notes
    2. Concentration of Measure and the Classical Theorems. The TSP and quick application of Azuma's inequality
    Easy size bounds
    Another mean Poissonization
    The Beardwood-Halton-Hammersly theorem
    Karp's partitioning algorithms
    Introduction to space-filling curve heuristic
    Asymptotics for the space-filling curve heuristic
    Additional notes
    3. More General Methods. Subadditive Euclidean functionals
    Examples. Good, bad and forthcoming
    A general L-(infinity) bound
    Simple subadditivity and geometric subadditivity
    A concentration inequality
    Minimal matching
    Two-sided bounds and first consequences
    Rooted duals and their applications
    Lower bounds and best possibilities
    Additional remarks
    4. Probability in Greedy Algorithms and Linear Programming. Assignment problem
    Simplex method for theoreticians
    Dyer-Frieze-McDiarmid inequality
    Dealing with integral constraints
    Distributional bounds
    Back to the future
    Additional remarks
    5. Distributional Techniques and the Objective Method. Motivation for a method
    Searching for a candidate object
    Topology for nice sets
    Information on the infinite tree
    Central limit theory
    Conditioning method for independence
    Dependency graphs and the CLT
    Additional remarks
    6. Talagrand's Isoperimetric Theory. Talagrand's isoperimetric theory
    Two geometric applications of the isoperimetric inequality
    Application to the longest-increasing-subsequence problem
    Proof of the isoperimetric problem
    Application and comparison in the theory of hereditary sets
    Suprema of linear functionals
    Tail of the assignment problem
    Further applications of Talagrand's isoperimetric inequalities
    Final considerations on related work

  • Author

    J. Michael Steele, Wharton School, University of Pennsylvania

Related Books

also by this author

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner Please see the permission section of the catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×
warning icon

Turn stock notifications on?

You must be signed in to your Cambridge account to turn product stock notifications on or off.

Sign in Create a Cambridge account arrow icon

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

Are you sure you want to delete your account?

This cannot be undone.


Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

Please fill in the required fields in your feedback submission.