Skip to content
Register Sign in Wishlist
The Sharpest Cut

The Sharpest Cut
The Impact of Manfred Padberg and His Work

$106.00 (C)

Part of MPS-SIAM Series on Optimization

  • 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: Hardback
  • isbn: 9780898715521

$ 106.00 (C)

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

Product filter button
About the Authors
  • The Sharpest Cut is written in honor of Manfred Padberg, who has made fundamental contributions to both the theoretical and computational sides of integer programming and combinatorial optimization. This outstanding collection presents recent results in these areas that are closely connected to Padberg's research. His deep commitment to the geometrical approach to combinatorial optimization can be felt throughout this volume; his search for increasingly better and computationally efficient cutting planes gave rise to its title. The peer-reviewed papers contained here are based on invited lectures given at a workshop held in October 2001 to celebrate Padberg's 60th birthday. Grouped by topic (packing, stable sets, and perfect graphs; polyhedral combinatorics; general polytopes; semidefinite programming; computation), many of the papers set out to solve challenges set forth in Padberg's work. The book also shows how Padberg's ideas on cutting planes have influenced modern commercial optimization software.

    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: Hardback
    • isbn: 9780898715521
    • length: 392 pages
    • dimensions: 260 x 185 x 25 mm
    • weight: 0.91kg
    • 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

    Part I: Manfred Padberg: Curriculum Vitae and Survey of His Work
    Chapter 1: Manfred Padberg: Curriculum Vitae
    Chapter 2: Time for Old and New Faces, L. Wolsey
    Part II: Packing, Stable Sets, and Perfect Graphs
    Chapter 3: Combinatorial Packing Problems, R. Borndörfer
    Chapter 4: Bicolorings and Equitable Bicolorings of Matrices, M. Conforti, G. Cornuéjols, and G. Zambelli
    Chapter 5: The Clique-Rank of 3-Chromatic Perfect Graphs, J. Fonlupt
    Chapter 6: On the Way to Perfection: Primal Operations for Stable Sets in Graphs, C. Gentile, U.-U. Haus, M. Köppe, G. Rinaldi, R. Weismantel
    Chapter 7: Relaxing Perfectness: Which Graphs Are “Almost” Perfect?, A.K. Wagler
    Part III: Polyhedral Combinatorics
    Chapter 8: Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes, M. Grötschel
    Chapter 9: (1,2)-Survivable Networks: Facets and Branch-and-Cut, H. Kerivin, A.R. Mahjoub, and C. Nocq
    Chapter 10: The Domino Inequalities for the Symmetric Traveling Salesman Problem, C. Naddef
    Chapter 11: Computing Optimal Consecutive Ones Matrices, M. Oswald and G. Reinelt
    Chapter 12: Protein Folding on Lattices: An Integer Programming Approach, V. Chandru, M.R. Rao, and G. Swaminathan
    Part IV: General Polytopes,
    Chapter 13: On the Expansion of Graphs of 0/1-Polytopes, V. Kaibel
    Chapter 14: Typical and Extremal Linear Programs, G.M. Ziegler
    Part V: Semidefinite Programming
    Chapter 15: A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations, C. Helmberg
    Chapter 16: Semidefinite Relaxations for Max-Cut, M. Laurent
    Part VI: Computation
    Chapter 17: The Steinberg Wiring Problem, N.W. Brixius and K.M. Anstreicher
    Chapter 18: Mixed-Integer Programming: A Progress Report, R.E. Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling
    Chapter 19: Graph Drawing: Exact Optimization Helps!, P. Muntzel and M. Jünger
    Part VII: Appendix
    Chapter 20: Dinner Speeches

  • Editor

    Martin Grötschel

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.