Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and HeuristicsAlgorithmic 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. |
Contents
| 1 | |
Deterministic Approaches | 143 |
Approximation Algorithms | 168 |
1 | 213 |
Randomized Algorithms | 307 |
1 | 376 |
Heuristics | 386 |
References | 414 |
Quantum Computing | 442 |
Other editions - View all
Common terms and phrases
algorithm design techniques approximation algorithms approximation ratio assignment Boolean function branch-and-bound clauses complexity concept consider constraints contains cost Hopt cover problem decision problem define Definition derandomization deterministic algorithm DNA computing edges efficient Exercise exponential feasible solution formula genetic algorithms given graph G greedy Hamiltonian cycle Hamiltonian tour hard problems input instance knapsack problem Las Vegas algorithm Lemma linear equations linear programming local optimum local search lower bounds matrix MAX-SAT method minimal Monte Carlo algorithm multigraph neighborhood NP-hard Observe Obviously optimal solution optimization problems output p₁ parameter parameterized polynomial polynomial-time algorithm polynomial-time approximation polytope positive integer prime Prob Prob(X problem instances proof prove pseudo-polynomial-time algorithms PTAS quadratic nonresidue quantum computation random variable randomized algorithm rithm satisfied search algorithm Section sequence simulated annealing solving Step Theorem U₁ V₁ vector vertex cover vertex cover problem vertices X₁