Tackling NP-hard problems

NP-hard problems were extensively discussed in Chapter 4, Designing Algorithms. Some NP-hard problems are important and we need to design algorithms to solve them.

If finding the solution for an NP-hard problem seems out of reach due to its complexity or the limitations of the available resources, we can take one of these approaches:

• Simplifying the problem

• Customizing a well-known solution to a similar problem

• Using a probabilistic method

Let's look into them one by one.

Simplifying the problem 

We can simplify the problem based on certain assumptions. The solved problem still gives a solution that is not perfect but is still insightful and useful. For this to work...