Algorithmics for Hard Problems

by Hromkovic, Juraj

• ISBN13: 9783540441342
• ISBN10: 3540441344
• Edition: 2nd
• Format: Hardcover
• Copyright: 2002-12-01
• Publisher: Springer-Nature New York Inc

Summary

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.

Table of Contents

Introduction	1	(10)
Elementary Fundamentals	11	(142)
Introduction	11	(2)
Fundamentals of Mathematics	13	(83)
Linear Algebra	13	(17)
Combinatorics, Counting, and Graph Theory	30	(16)
Boolean Functions and Formulae	46	(9)
Algebra and Number Theory	55	(27)
Probability Theory	82	(14)
Fundamentals of Algorithmics	96	(57)
Alphabets, Words, and Languages	96	(3)
Algorithmic Problems	99	(17)
Complexity Theory	116	(21)
Algorithm Design Techniques	137	(16)
Deterministic Approaches	153	(100)
Introduction	153	(3)
Pseudo-Polynomial-Time Algorithms	156	(18)
Basic Concept	156	(2)
Dynamic Programming and Knapsack Problem	158	(3)
Maximum Flow Problem and Ford-Fulkerson Method	161	(11)
Limits of Applicability	172	(2)
Parameterized Complexity	174	(6)
Basic Concept	174	(1)
Applicability of Parameterized Complexity	175	(3)
Discussion	178	(2)
Branch-and-Bound	180	(9)
Basic Concept	180	(1)
Applications for Max-Sat and TSP	181	(6)
Discussion	187	(2)
Lowering Worst Case Complexity of Exponential Algorithms	189	(5)
Basic Concept	189	(1)
Solving 3SAT in Less than 2n Complexity	190	(4)
Local Search	194	(20)
Introduction and Basic Concept	194	(4)
Examples of Neighborhoods and Kernighan-Lin's Variable-Depth Search	198	(5)
Tradeoffs Between Solution Quality and Complexity	203	(11)
Relaxation to Linear Programming	214	(35)
Basic Concept	214	(2)
Expressing Problems as Linear Programming Problems	216	(7)
The Simplex Algorithm	223	(10)
Rounding, LP-Duality and Primal-Dual Method	233	(16)
Bibliographical Remarks	249	(4)
Approximation Algorithms	253	(94)
Introduction	253	(1)
Fundamentals	254	(12)
Concept of Approximation Algorithms	254	(5)
Classification of Optimization Problems	259	(1)
Stability of Approximation	260	(4)
Dual Approximation Algorithms	264	(2)
Algorithm Design	266	(55)
Introduction	266	(2)
Cover Problems, Greedy Method, and Relaxation to Linear Programming	268	(8)
Maximum Cut Problem and Local Search	276	(3)
Knapsack Problem and PTAS	279	(9)
Traveling Salesperson Problem and Stability of Approximation	288	(25)
Bin-Packing, Scheduling, and Dual Approximation Algorithms	313	(8)
Inapproximability	321	(22)
Introduction	321	(2)
Reduction to NP-Hard Problems	323	(2)
Approximation-Preserving Reductions	325	(9)
Probabilistic Proof Checking and Inapproximability	334	(9)
Bibliographical Remarks	343	(4)
Randomized Algorithms	347	(92)
Introduction	347	(2)
Classification of Randomized Algorithms and Design Paradigms	349	(20)
Fundamentals	349	(2)
Classification of Randomized Algorithms	351	(14)
Paradigms of Design of Randomized Algorithms	365	(4)
Design of Randomized Algorithms	369	(50)
Introduction	369	(1)
Quadratic Residues, Random Sampling, and Las Vegas	370	(5)
Primality Testing, Abundance of Witnesses, and One-Sided-Error Monte Carlo	375	(17)
Some Equivalence Tests, Fingerprinting, and Monte Carlo	392	(7)
Randomized Optimization Algorithms for Min-Cut	399	(8)
Max-Sat, Random Sampling, and Relaxation to Linear Programming with Random Rounding	407	(8)
3SAT and Randomized Multistart Local Search	415	(4)
Derandomization	419	(16)
Fundamental Ideas	419	(2)
Derandomization by the Reduction of the Probability Space Size	421	(4)
Reduction of the Size of the Probability Space and Max-EkSat	425	(3)
Derandomization by the Method of Conditional Probabilities	428	(2)
Method of Conditional Probabilities and Satisfiability Problems	430	(5)
Bibliographical Remarks	435	(4)
Heuristics	439	(30)
Introduction	439	(2)
Simulated Annealing	441	(11)
Basic Concept	441	(4)
Theory and Experience	445	(4)
Randomized Tabu Search	449	(3)
Genetic Algorithms	452	(14)
Basic Concept	452	(8)
Adjustment of Free Parameters	460	(6)
Bibliographical Remarks	466	(3)
A Guide to Solving Hard Problems	469	(42)
Introduction	469	(1)
Taking over an Algorithmic Task or a Few Words about Money	470	(1)
Combining Different Concepts and Techniques	471	(3)
Comparing Different Approaches	474	(2)
Speedup by Parallelization	476	(9)
New Technologies	485	(14)
Introduction	485	(1)
DNA Computing	486	(8)
Quantum Computing	494	(5)
Glossary of Basic Terms	499	(12)
References	511	(22)
Index	533