HomeGroupsTalkMoreZeitgeist
This site uses cookies to deliver our services, improve performance, for analytics, and (if not signed in) for advertising. By using LibraryThing you acknowledge that you have read and understand our Terms of Service and Privacy Policy. Your use of the site and services is subject to these policies and terms.
Hide this

Results from Google Books

Click on a thumbnail to go to Google Books.

Probability Theory and Combinatorial…
Loading...

Probability Theory and Combinatorial Optimization (CBMS-NSF Regional… (original 1997; edition 1987)

by J. Michael Steele (Author)

MembersReviewsPopularityAverage ratingConversations
9None1,578,406 (3.5)None
This monograph 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 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. There are three fundamental probabilistic themes that are examined through our concrete investigations. First, there is a systematic exploitation of martingales. Over the last ten years, many investigators of problems of combinatorial optimization have come to count on martingale inequalities as versatile tools which let us show that many of the naturally occurring random variables of combinatorial optimization are sharply concentrated about their means - a phenomenon with numerous practical and theoretical consequences. The second theme that is explored is the systematic use of subadditivity of several flavors, ranging from the na#65533;ve subadditivity of real sequences to the subtler subadditivity of stochastic processes. By and large, subadditivity offers only elementary tools, but on remarkably many occasions such tools provide the key organizing principle in the attack on problems of nearly intractable difficulty. The third and deepest theme developed here concerns the application of Talagrand's isoperimetric theory of concentration inequalities. This new theory is reshaping almost everything that is known in the probability theory of combinatorial optimization. The treatment given here deals with only a small part of Talagrand's theory, but the reader will find considerable coaching on how to use some of the most important ideas from that theory.… (more)
Member:ibsdimag
Title:Probability Theory and Combinatorial Optimization (CBMS-NSF Regional Conference Series in Applied Mathematics)
Authors:J. Michael Steele (Author)
Info:Society for Industrial and Applied Mathematics (1987), 167 pages
Collections:Your library
Rating:
Tags:None

Work details

Probability Theory and Combinatorial Optimization by J. Michael Steele (1997)

None.

None
Loading...

Sign up for LibraryThing to find out whether you'll like this book.

No current Talk conversations about this book.

No reviews
no reviews | add a review
You must log in to edit Common Knowledge data.
For more help see the Common Knowledge help page.
Canonical title
Original title
Alternative titles
Original publication date
People/Characters
Important places
Important events
Related movies
Awards and honors
Epigraph
Dedication
First words
Quotations
Last words
Disambiguation notice
Publisher's editors
Blurbers
Original language
Canonical DDC/MDS

References to this work on external resources.

Wikipedia in English (1)

This monograph 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 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. There are three fundamental probabilistic themes that are examined through our concrete investigations. First, there is a systematic exploitation of martingales. Over the last ten years, many investigators of problems of combinatorial optimization have come to count on martingale inequalities as versatile tools which let us show that many of the naturally occurring random variables of combinatorial optimization are sharply concentrated about their means - a phenomenon with numerous practical and theoretical consequences. The second theme that is explored is the systematic use of subadditivity of several flavors, ranging from the na#65533;ve subadditivity of real sequences to the subtler subadditivity of stochastic processes. By and large, subadditivity offers only elementary tools, but on remarkably many occasions such tools provide the key organizing principle in the attack on problems of nearly intractable difficulty. The third and deepest theme developed here concerns the application of Talagrand's isoperimetric theory of concentration inequalities. This new theory is reshaping almost everything that is known in the probability theory of combinatorial optimization. The treatment given here deals with only a small part of Talagrand's theory, but the reader will find considerable coaching on how to use some of the most important ideas from that theory.

No library descriptions found.

Book description
Haiku summary

Quick Links

Popular covers

Rating

Average: (3.5)
0.5
1
1.5
2
2.5
3 1
3.5
4 1
4.5
5

Is this you?

Become a LibraryThing Author.

 

About | Contact | Privacy/Terms | Help/FAQs | Blog | Store | APIs | TinyCat | Legacy Libraries | Early Reviewers | Common Knowledge | 155,640,316 books! | Top bar: Always visible