Happy holidays from us to you—get up to $30 off your next print or eBook! Shop now >>

Complexity and Approximation

Combinatorial Optimization Problems and Their Approximability Properties

Authors: Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.

Buy this book

eBook $64.99
price for USA in USD (gross)
  • ISBN 978-3-642-58412-1
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $119.00
price for USA in USD
  • ISBN 978-3-540-65431-5
  • with online files
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $84.99
price for USA in USD
  • ISBN 978-3-642-63581-6
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this Textbook

N COMPUTER applications we are used to live with approximation. Var­ I ious notions of approximation appear, in fact, in many circumstances. One notable example is the type of approximation that arises in numer­ ical analysis or in computational geometry from the fact that we cannot perform computations with arbitrary precision and we have to truncate the representation of real numbers. In other cases, we use to approximate com­ plex mathematical objects by simpler ones: for example, we sometimes represent non-linear functions by means of piecewise linear ones. The need to solve difficult optimization problems is another reason that forces us to deal with approximation. In particular, when a problem is computationally hard (i. e. , the only way we know to solve it is by making use of an algorithm that runs in exponential time), it may be practically unfeasible to try to compute the exact solution, because it might require months or years of machine time, even with the help of powerful parallel computers. In such cases, we may decide to restrict ourselves to compute a solution that, though not being an optimal one, nevertheless is close to the optimum and may be determined in polynomial time. We call this type of solution an approximate solution and the corresponding algorithm a polynomial-time approximation algorithm. Most combinatorial optimization problems of great practical relevance are, indeed, computationally intractable in the above sense. In formal terms, they are classified as Np-hard optimization problems.

Table of contents (10 chapters)

  • The Complexity of Optimization Problems

    Ausiello, Giorgio (et al.)

    Pages 1-37

  • Design Techniques for Approximation Algorithms

    Ausiello, Giorgio (et al.)

    Pages 39-85

  • Approximation Classes

    Ausiello, Giorgio (et al.)

    Pages 87-122

  • Input-Dependent and Asymptotic Approximation

    Ausiello, Giorgio (et al.)

    Pages 123-151

  • Approximation through Randomization

    Ausiello, Giorgio (et al.)

    Pages 153-174

Buy this book

eBook $64.99
price for USA in USD (gross)
  • ISBN 978-3-642-58412-1
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Hardcover $119.00
price for USA in USD
  • ISBN 978-3-540-65431-5
  • with online files
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Softcover $84.99
price for USA in USD
  • ISBN 978-3-642-63581-6
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Complexity and Approximation
Book Subtitle
Combinatorial Optimization Problems and Their Approximability Properties
Authors
Copyright
1999
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-642-58412-1
DOI
10.1007/978-3-642-58412-1
Hardcover ISBN
978-3-540-65431-5
Softcover ISBN
978-3-642-63581-6
Edition Number
1
Number of Pages
XX, 524
Topics