Skip to content
Register Sign in Wishlist
An Algorithmic Theory of Numbers, Graphs and Convexity

An Algorithmic Theory of Numbers, Graphs and Convexity

Part of CBMS-NSF Regional Conference Series in Applied Mathematics

  • Date Published: February 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: 9780898712032


Add to wishlist

Looking for an inspection copy?

This title is not currently available on inspection

Product filter button
About the Authors
  • A study of how complexity questions in computing interact with classical mathematics in the numerical analysis of issues in algorithm design. Algorithmic designers concerned with linear and nonlinear combinatorial optimization will find this volume especially useful. Two algorithms are studied in detail: the ellipsoid method and the simultaneous diophantine approximation method. Although both were developed to study, on a theoretical level, the feasibility of computing some specialized problems in polynomial time, they appear to have practical applications. The book first describes use of the simultaneous diophantine method to develop sophisticated rounding procedures. Then a model is described to compute upper and lower bounds on various measures of convex bodies. Use of the two algorithms is brought together by the author in a study of polyhedra with rational vertices. The book closes with some applications of the results to combinatorial optimization.

    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: February 1987
    • format: Paperback
    • isbn: 9780898712032
    • length: 97 pages
    • dimensions: 253 x 172 x 6 mm
    • weight: 0.188kg
    • 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

    How to Round Numbers
    Preliminaries: On Algorithms Involving Numbers
    Diophantine Approximation, Problems
    Lattices, Bases, and the Reduction Problem
    Diophantine Approximation and Rounding
    What is a Real Number How to Round a Convex Body
    Preliminaries: Inputting a Set
    Algorithmic Problems on Convex Sets
    The Ellipsoid Method
    Rational Polyhedra
    Some Other Algorithmic Problems on Convex Sets
    Integer Programming in Fixed Dimension
    Some Applications in Combinatorics
    Cuts and Joins
    Chromatic Number, Cliques and Perfect Graphs
    Minimizing a Submodular Function.

  • Author

    Laszlo Lovasz, Eötvös Loránd University, Budapest

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.