or_algorithms

1. Exact pattern matching

• Naive algorithm |
• Rabin-Karp algorithm | in average, at worst
• Knuth–Morris–Pratt algorithm |

Benchmark results can be found here.

2. 0-1 knapsack problem

• Dynamic programming algorithm
• Approximation algorithms
  • 2-Approximation
  • FPTAS
• Least Cost B&B algorithm

Benchmark results can be found here.

3. Genetic Algorithms

• Knapsack problem
• Travelling salesman problem

Benchmark results can be found here.

4. Quadratic assignment problem

• Local search - best improvement
• Iterated local search - stochastic k-opt

Benchmark results can be found here.

5. Cell formation problem

• Simulated annealing

Benchmark results can be found here.