Skip to content
Register Sign in Wishlist

Iterative Methods in Combinatorial Optimization

$54.99 (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

$ 54.99 (P)

Add to cart Add to wishlist

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 providing details of the course you are teaching.

Product filter button
About the Authors
  • 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.

    • 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
    Read more

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

  • Authors

    Lap Chi Lau, The Chinese University of Hong Kong
    Lap-Chi Lau is an Assistant Professor in the Department of Computer Science and Engineering at The Chinese University of Hong Kong. Lap-Chi's main research interests are in combinatorial optimization and graph algorithms. His paper on Steiner tree packing was given the Machtey award in the IEEE Foundations of Computer Science Conference. His Ph.D. thesis was awarded the Doctoral Prize from the Canadian Mathematical Society and a Doctoral Prize from the Natural Sciences and Engineering Research Council of Canada.

    R. Ravi, Carnegie Mellon University, Pennsylvania
    R. Ravi is Carnegie Bosch Professor of Operations Research and Computer Science at Carnegie Mellon University. Ravi's main research interests are in combinatorial optimization (particularly in approximation algorithms), computational molecular biology and electronic commerce. He is currently on the editorial boards of Management Science and the ACM Transactions on Algorithms.

    Mohit Singh, McGill University, Montréal
    Mohit Singh is an Assistant Professor in the School of Computer Science, McGill University. He completed his Ph.D. in 2008 at the Tepper School of Business, Carnegie Mellon University, where his advisor was Professor R. Ravi. His thesis was awarded the Tucker prize by the Mathematical Programming Society. His research interests include approximation algorithms, combinatorial optimization and studying models that deal with uncertainty in data.

Sign In

Please sign in to access your account


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

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 ×

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.