Algorithmics for Hard Problems [Hardcover]

Juraj Hromkovic (Author)

Book Description

ISBN-10: 3540441344 | ISBN-13: 978-3540441342 | Publication Date: November 19, 2002 | Edition: 2nd

There are several approaches to attack hard problems. All have their merits, but also their limitations, and need a large body of theory as their basis. A number of books for each one exist: books on complexity theory, others on approximation algorithms, heuristic approaches, parametrized complexity, and yet others on randomized algorithms. This book discusses thoroughly all of the above approaches. And, amazingly, at the same time, does this in a style that makes the book accessible not only to theoreticians, but also to the non-specialist, to the student or teacher, and to the programmer. Do you think that mathematical rigor and accessibility contradict? Look at this book to find out that they do not, due to the admirable talent of the author to present his material in a clear and concise way, with the idea behind the approach spelled out explicitly, often with a revealing example. Reading this book is a beautiful experience and I can highly recommend it to anyone interested in learning how to solve hard problems. It is not just a condensed union of material from other books. Because it discusses the different approaches in depth, it has the chance to compare them in detail, and, most importantly, to highlight under what circumstances which approach might be worth exploring. No book on a single type of solution can do that, but this book does it in an absolutely fascinating way that can serve as a pattern for theory textbooks with a high level of generality. (Peter Widmayer) The second edition extends the part on the method of relaxation to linear programming with an emphasis on rounding, LP-duality, and primal-dual schema, and provides a self-contained and transparent presentation of the design of randomized algorithms for primality testing.

Editorial Reviews

From the Back Cover

There are several approaches to attack hard problems. All have their merits, but also their limitations, and need a large body of theory as their basis. A number of books for each one exist: books on complexity theory, others on approximation algorithms, heuristic approaches, parametrized complexity, and yet others on randomized algorithms. This book discusses thoroughly all of the above approaches. And, amazingly, at the same time, does this in a style that makes the book accessible not only to theoreticians, but also to the non-specialist, to the student or teacher, and to the programmer. Do you think that mathematical rigor and accessibility contradict? Look at this book to find out that they do not, due to the admirable talent of the author to present his material in a clear and concise way, with the idea behind the approach spelled out explicitly, often with a revealing example. Reading this book is a beautiful experience and I can highly recommend it to anyone interested in learning how to solve hard problems. It is not just a condensed union of material from other books. Because it discusses the different approaches in depth, it has the chance to compare them in detail, and, most importantly, to highlight under what circumstances which approach might be worth exploring. No book on a single type of solution can do that, but this book does it in an absolutely fascinating way that can serve as a pattern for theory textbooks with a high level of generality. (Peter Widmayer) The second edition extends the part on the method of relaxation to linear programming with an emphasis on rounding, LP-duality, and primal-dual schema, and provides a self-contained and transparent presentation of the design of randomized algorithms for primality testing.

Product Details

• Hardcover: 557 pages
• Publisher: Springer; 2nd edition (November 19, 2002)
• Language: English
• ISBN-10: 3540441344
• ISBN-13: 978-3540441342
• Product Dimensions: 9.3 x 6.2 x 1.3 inches
• Shipping Weight: 2 pounds
• Average Customer Review: 2.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #711,255 in Books (See Top 100 in Books)
  • #19 in Books > Computers & Technology > Computer Science > Artificial Intelligence > Heuristic & Constrained Search

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

10 of 11 people found the following review helpful:

4.0 out of 5 stars Good Book for Advanced Computing, February 12, 2003

By A Customer

This review is from: Algorithmics for Hard Computing Problems (Hardcover)

Algorithmics for Hard Problems addresses an important (if somewhat small) group of technical people who work exclusively on intractable problems. It takes a great deal of creativity and a large set of intellectual tools to make even modest progress on these problems. Prof. Hromkovic's book presents and organizes a big package of ideas and tools for approaching these problems. Even the last section, entitled "A Guide to Solving Hard Problems" addresses some of the practical issues of working on problems for which a completely satisfactory answer may be out of reach.

This book is especially helpful for software professionals solving difficult problems because it helps one to categorize and understand where the "pain points" can be found. In many software applications very hard problems are hidden within perfectly reasonable appearing and seemingly benign systems -- it's critical in these cases to correctly project the details of the problem onto a well defined set of basis tasks.

3 of 4 people found the following review helpful:

1.0 out of 5 stars Best to avoid this one . . ., September 3, 2008

By 

Reader - See all my reviews

Amazon Verified Purchase

This review is from: Algorithmics for Hard Problems (Hardcover)

This book's presentation is difficult if not impossible to understand. The algorithmics are simply lost amid highly dense, nearly incomprehensible symbolism that obscures rather than illuminates ideas. As a result, the book requires tremendous effort to move from page to page. It will therefore be of limited or no use to practicing software professionals. Although the price is right, I cannot recommend this book.