This textbook provides a "cheap ticket" to the design of algorithms for hard
computing problems, Le., for problems for which no low-degree polynomial-time
algorithms1 are known. It focuses on a systematic presentation of the fundamental
concepts and algorithm design techniques. The
presentation of these concepts and techniques starts with some fundamental
informal ideas that are later consecutively specified in detail. The algorithms
used to illustrate the application of these methods are chosen with respect to
their simplicity and transparency rather than with respect to their quality (complexity
and reliability).

lgrsnf/A:/compressed/10.1007%2F978-3-662-04616-6.pdf

nexusstc/Algorithmics for Hard Problems/e06b3775fb75234431e2020d1fdee9e0.pdf

scihub/10.1007/978-3-662-04616-6.pdf

zlib/Computers/Algorithms and Data Structures/Juraj Hromkovič/Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics_2099580.pdf

J. (RWTH Aachen, Germany) Hromkovic

Wilfried Brauer

Springer Spektrum. in Springer-Verlag GmbH

Steinkopff. in Springer-Verlag GmbH

Texts in Theoretical Computer Science An EATCS Series, Berlin, Heidelberg, 2001

Texts in Theoretical Computer Science. An EATCS Series, 1st, 2001

Germany, Germany

1, 20130314

uuuu

0

lg945694

{"container_title":"Texts in Theoretical Computer Science An EATCS Series","edition":"1","isbns":["3662046164","3662046180","9783662046166","9783662046180"],"issns":["1862-4499"],"last_page":500,"publisher":"Springer","series":"Texts in Theoretical Computer Science. An EATCS Series"}

Algorithmic design, especially for hard problems, is more essential for success in solving them than any standard improvement of current computer technologies. Because of this, the design of algorithms for solving hard problems is the core of current algorithmic research from the theoretical point of view as weIl as from the practical point of view. There are many general textbooks on algorithmics, and several specialized books devoted to particular approaches such as local search, randomization, approximation algorithms, or heuristics. But there is no textbook that focuses on the design of algorithms for hard computing tasks, and that systematically explains, combines, and compares the main possibilities for attacking hard algorithmic problems. As this topic is fundamental for computer science, this book tries to elose this gap. Another motivation, and probably the main reason for writing this book, is connected to education. The considered area has developed very dynamically in recent years and the research on this topic discovered several profound re­ sults, new concepts, and new methods. Some of the achieved contributions are so fundamental that one can speak about paradigms which should be ineluded in the education of every computer science student. Unfortunately, this is very far from reality. This is because these paradigms are not sufficiently known in the computer science community, and so they are insufficiently communicated to students and practitioners.

This book is an introduction to the methods of designing algorithms for hard computing tasks. This area has developed very dynamically in the last years and is one of the kernels of current research in algorithm and complexity theory. The book mainly concentrates on approximate, randomized and heuristic algorithms, and on the theoretical and experimental comparison of these approaches according to the requirements of the practice. There exist several monographs specializing in some of these methods, but no book systematically explains and compares all main possibilities of attacking hard computing problems. Since the topic is fundamental for the university study in computer science and essential for the transfer of formal methods to the practice, the aim of the book is to close this gap by providing at once a textbook for graduate students and a handbook for practitioners dealing with hard computing problems

Front Matter....Pages I-XI
Introduction....Pages 1-9
Elementary Fundamentals....Pages 11-142
Deterministic Approaches....Pages 143-212
Approximation Algorithms....Pages 213-305
Randomized Algorithms....Pages 307-385
Heuristics....Pages 387-415
A Guide to Solving Hard Problems....Pages 417-457
Back Matter....Pages 459-494

2013-08-01