[prev] 144 [next]

Randomised Algorithms for NP-Problems

Many NP-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