Iterative Methods in Combinatorial Optimization
$57.00 (P)
Part of Cambridge Texts in Applied Mathematics
- Authors:
- Lap Chi Lau, The Chinese University of Hong Kong
- R. Ravi, Carnegie Mellon University, Pennsylvania
- Mohit Singh, McGill University, Montréal
- Date Published: April 2011
- availability: Available
- format: Paperback
- isbn: 9780521189439
$
57.00
(P)
Paperback
Other available formats:
Hardback, eBook
Looking for an examination copy?
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.
-
With the advent of approximation algorithms for NP-hard combinatorial optimization problems, several techniques from exact optimization such as the primal-dual method have proven their staying power and versatility. This book describes a simple and powerful method that is iterative in essence, and similarly useful in a variety of settings for exact and approximate optimization. The authors highlight the commonality and uses of this method to prove a variety of classical polyhedral results on matchings, trees, matroids, and flows. The presentation style is elementary enough to be accessible to anyone with exposure to basic linear algebra and graph theory, making the book suitable for introductory courses in combinatorial optimization at the upper undergraduate and beginning graduate levels. Discussions of advanced applications illustrate their potential for future application in research in approximation algorithms.
Read more- Presents a unified way of looking at several problems
- Offers new ways of deriving classical results in optimization
- Provides extensions to hard variants of classical problems
- Offers elementary presentation appealing to a broad mathematically interested audience
Customer reviews
Not yet reviewed
Be the first to review
Review was not posted due to profanity
×Product details
- Date Published: April 2011
- format: Paperback
- isbn: 9780521189439
- length: 256 pages
- dimensions: 229 x 153 x 15 mm
- weight: 0.36kg
- contains: 44 b/w illus. 102 exercises
- availability: Available
Table of Contents
1. Introduction
2. Preliminaries
3. Matching and vertex cover in bipartite graphs
4. Spanning trees
5. Matroids
6. Arborescence and rooted connectivity
7. Submodular flows and applications
8. Network matrices
9. Matchings
10. Network design
11. Constrained optimization problems
12. Cut problems
13. Iterative relaxation: early and recent examples
14. Summary.
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» Proceed