Benoit A., Robert Y., Vivien F. A Guide to Algorithm Design. Paradigms, Methods and Complexity Analysis

Boca Raton: CRC Press, 2014. — 359 p.ExercisesPolynomial-time algorithms
On the complexity to compute
Exercises
Solutions to exercises
Bibliographical notes
Strassen's algorithm
Master theorem
Solving recurrences
Exercises
Solutions to exercises
Bibliographical notes
Motivating example: The sports hall
Designing greedy algorithms
Graph coloring
Theory of matroids
Exercises
Solutions to exercises
Bibliographical notes
The coin changing problem
The knapsack problem
Designing dynamic-programming algorithms
Exercises
Solutions to exercises
Bibliographical notes
Methods for amortized analysis
Exercises
Solutions to exercises
Bibliographical notes
NP-completeness & beyond
A practical approach to complexity theory
Problem classes
NP-complete problems and reduction theory
Examples of NP-complete problems and reductions
Importance of problem de nition
Strong NP-completeness
Bibliographical notes
Easy reductions
About graph coloring
Scheduling problems
More involved reductions
Solutions to exercises
Bibliographical notes
Approximation results
Polynomial problem instances
Linear programming
Randomized algorithms
Branch-and-bound and backtracking
Bibliographical notes
Approximation results
Dealing with NP-complete problems
Solutions to exercises
Bibliographical notes
Reasoning on problem complexity
Basic reasoning
Set of problems with polynomial-time algorithms
Set of NP-complete problems
Optimal algorithms for homogeneous resources
Variants of the problem
Extension to a clique of heterogeneous resourcesReplica placement in tree networks
Access policies
Complexity results
Variants of the replica placement problemPacket routing
Maximum edge-disjoint paths
Packet routing with variable-pathsMatrix product, or tiling the unit square
Problem motivation
NP-completeness
A guaranteed heuristic
Related problems
Online scheduling
Flow time optimization
Competitive analysis
Makespan optimizationRefs