A guide to algorithm design paradigms, methods, and complexity analysis
| Main Authors: | , , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Boca Raton
CRC Press
2014
|
| Series: | Chapman & Hall/CRC Applied Algorithms and Data Structures series
|
| Subjects: | |
| Online Access: | |
| Collection: | O'Reilly - Collection details see MPG.ReNa |
Table of Contents:
- 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