[prev] 47 [next]

Randomised Algorithms for NP-hard Problems

Many NP-hard problems can be tackled by randomised algorithms that
  • compute nearly optimal solutions
    • with high probability
Examples:
  • travelling salesman
  • constraint satisfaction problems, satisfiability
  • … and many more