Algorithmics for Hard Computing Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics

by Hromkovic, Juraj

• ISBN13: 9783540668602
• ISBN10: 3540668608
• Format: Hardcover
• Copyright: 2001-07-01
• Publisher: Springer Verlag

Summary

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.

Table of Contents

Introduction	1	(10)
Elementary Fundamentals	11	(132)
Introduction	11	(2)
Fundamentals of Mathematics	13	(73)
Linear Algebra	13	(17)
Combinatorics, Counting, and Graph Theory	30	(16)
Boolean Functions and Formulae	46	(9)
Algebra and Number Theory	55	(18)
Probability Theory	73	(13)
Fundamentals of Algorithmics	86	(57)
Alphabets, Words, and Languages	86	(4)
Algorithmic Problems	90	(17)
Complexity Theory	107	(21)
Algorithm Design Techniques	128	(15)
Deterministic Approaches	143	(70)
Introduction	143	(3)
Pseudo-Polynomial-Time Algorithms	146	(7)
Basic Concept	146	(2)
Dynamic Programming and Knapsack Problem	148	(3)
Limits of Applicability	151	(2)
Parameterized Complexity	153	(6)
Basic Concept	153	(2)
Applicability of Parameterized Complexity	155	(3)
Discussion	158	(1)
Branch-and-Bound	159	(9)
Basic Concept	159	(2)
Applications for MAX-SAT and TSP	161	(6)
Discussion	167	(1)
Lowering Worst Case Complexity of Exponential Algorithms	168	(5)
Basic Concept	168	(1)
Solving 3SAT in Less than 2n Complexity	169	(4)
Local Search	173	(20)
Introduction and Basic Concept	173	(4)
Examples of Neighborhoods and Kernighan-Lin's Variable-Depth Search	177	(5)
Tradeoffs Between Solution Quality and Complexity	182	(11)
Relaxation to Linear Programming	193	(16)
Basic Concept	193	(2)
Expressing Problems as Linear Programming Problems	195	(4)
The Simplex Algorithm	199	(10)
Bibliographical Remarks	209	(4)
Approximation Algorithms	213	(94)
Introduction	213	(1)
Fundamentals	214	(12)
Concept of Approximation Algorithms	214	(4)
Classification of Optimization Problems	218	(1)
Stability of Approximation	219	(5)
Dual Approximation Algorithms	224	(2)
Algorithm Design	226	(55)
Introduction	226	(1)
Cover Problems, Greedy Method, and Relaxation to Linear Programming	227	(8)
Maximum Cut Problem and Local Search	235	(3)
Knapsack Problems and PTAS	238	(10)
Traveling Salesperson Problem and Stability of Approximation	248	(25)
Bin-Packing, Scheduling, and Dual Approximation Algorithms	273	(8)
Inapproximability	281	(22)
Introduction	281	(1)
Reduction to NP-Hard Problems	282	(2)
Approximation-Preserving Reductions	284	(10)
Probabilistic Proof Checking and Inapproximability	294	(9)
Bibliographical Remarks	303	(4)
Randomized Algorithms	307	(80)
Introduction	307	(2)
Classification of Randomized Algorithms and Design Paradigms	309	(20)
Fundamentals	309	(2)
Classification of Randomized Algorithms	311	(14)
Paradigms of Design of Randomized Algorithms	325	(4)
Design of Randomized Algorithms	329	(38)
Introduction	329	(1)
Quadratic Residues, Random Sampling, and Las Vegas	330	(5)
Primality Testing, Abundance of Witnesses, and One-Sided-Error Monte Carlo	335	(7)
Some Equivalence Tests, Fingerprinting, and Monte Carlo	342	(6)
Randomized Optimization Algorithms for MIN-CUT	348	(9)
MAX-SAT, Random Sampling, and Relaxation to Linear Programming with Random Rounding	357	(6)
3SAT and Randomized Multistart Local Search	363	(4)
Derandomization	367	(16)
Fundamental Ideas	367	(2)
Derandomization by the Reduction of the Probability Space Size	369	(5)
Reduction of the Size of the Probability Space and MAX-EkSAT	374	(2)
Derandomization by the Method of Conditional Probabilities	376	(3)
Method of Conditional Probabilities and Satisfiability Problems	379	(4)
Bibliographical Remarks	383	(4)
Heuristics	387	(30)
Introduction	387	(2)
Simulated Annealing	389	(11)
Basic Concept	389	(4)
Theory and Experience	393	(4)
Randomized Tabu Search	397	(3)
Genetic Algorithms	400	(14)
Basic Concept	400	(8)
Adjustment of Free Parameters	408	(6)
Bibliographical Remarks	414	(3)
A Guide to Solving Hard Problems	417	(42)
Introduction	417	(1)
Taking over an Algorithmic Task or a Few Words about Money	418	(1)
Combining Different Concepts and Techniques	419	(3)
Comparing Different Approaches	422	(2)
Speedup by Parallelization	424	(9)
New Technologies	433	(14)
Introduction	433	(1)
DNA Computing	434	(8)
Quantum Computing	442	(5)
Glossary of Basic Terms	447	(12)
References	459	(22)
Index	481