A guide to algorithm design : paradigms, methods, and complexity analysis / Anne Benoit, Yves Robert, and Frederick Vivien.

Includes bibliographical references and index.

And Bibliographic Notes appear at the end of each chapter in this section. NP-Completeness and Beyond ; NP-Completeness ; A practical approach to complexity theory; Problem classes; NP-complete problems and reduction theory; Examples of NP-complete problems and reductions; Importance of problem definition; Strong NP-completeness; Why does it matter? Exercises on NP-Completeness; Easy reductions; About graph coloring; Scheduling problems; More involved reductions; 2-PARTITION is NP-complete Beyond NP-Completeness ; Approximation results; Polynomial problem instances; Linear programming; Randomized algorithms; Branch-and-bound and backtracking Exercises Going beyond NP-Completeness ; Approximation results; Dealing with NP-complete problems Reasoning on Problem Complexity ; Reasoning to Assess a Problem Complexity ; Basic Reasoning; Set of problems with polynomial-time algorithms; Set of NP-complete problems Chains-on-Chains Partitioning ; Optimal algorithms for homogeneous resources; Variants of the problem; Extension to a clique of heterogeneous resources; Conclusion Replica Placement in Tree Networks ; Access policies; Complexity results; Variants of the replica placement problem; Conclusion Packet Routing ; MEDP: Maximum edge-disjoint paths; PRVP: Packet routing with variable-paths; Conclusion Matrix Product, or Tiling the Unit Square ; Problem motivation; NP-completeness; A guaranteed heuristic; Related problems Online Scheduling ; Flow time optimization; Competitive analysis; Makespan optimization; Conclusion Bibliography Index Polynomial-Time Algorithms: Exercises; Introduction to Complexity; On the complexity to compute xn ; Asymptotic notations: O, o, Θ, and Ω Divide-and-Conquer ; Strassen's algorithm; Master theorem; Solving recurrences Greedy Algorithms ; Motivating example: the sports hall; Designing greedy algorithms; Graph coloring; Theory of matroids Dynamic Programming ; The coin changing problem; The knapsack problem; Designing dynamic-programming algorithms Amortized Analysis ; Methods for amortized analysis Exercises, Solutions

Polynomial-Time Algorithms: Exercises Introduction to Complexity On the complexity to compute xnAsymptotic notations: O, o, Θ, and ΩDivide-and-Conquer Strassen's algorithm Master theorem Solving recurrencesGreedy Algorithms Motivating example: the sports hall Designing greedy algorithms Graph coloringTheory of matroidsDynamic Programming The coin changing problem The knapsack problem Designing dynamic-programming algorithmsAmortized AnalysisMethods for amortized analysisExercises, Solutions, and Bibliographic Notes appear at the end of each chapter in this section. NP-Completeness and Beyond NP.