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

Probability Theory and Combinatorial Optimization

$53.00 (P)

Part of CBMS-NSF Regional Conference Series in Applied Mathematics

  • Date Published: January 1987
  • availability: This item is not supplied by Cambridge University Press in your region. Please contact Soc for Industrial & Applied Mathematics for availability.
  • format: Paperback
  • isbn: 9780898713800

$ 53.00 (P)
Paperback

This item is not supplied by Cambridge University Press in your region. Please contact Soc for Industrial & Applied Mathematics for availability.
Unavailable Add to wishlist

Looking for an examination copy?

This title is not currently available for examination. However, if you are interested in the title for your course we can consider offering an examination copy. To register your interest please contact collegesales@cambridge.org providing details of the course you are teaching.

Description
Product filter button
Description
Contents
Resources
Courses
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: January 1987
    • format: Paperback
    • isbn: 9780898713800
    • length: 167 pages
    • dimensions: 250 x 177 x 9 mm
    • weight: 0.304kg
    • availability: This item is not supplied by Cambridge University Press in your region. Please contact Soc for Industrial & Applied Mathematics for availability.
  • Table of Contents

    Preface
    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
    Dénoument
    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
    Bibliography
    Index.

  • Author

    J. Michael Steele, Wharton School, University of Pennsylvania

Sign In

Please sign in to access your account

Cancel

Not already registered? Create an account now. ×

Sorry, this resource is locked

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

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 www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×

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.

Cancel

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.
×