Introduction When we are faced with a combinatorial optimization problem, our goal is to design an algorithm that satisfies three important properties. (1) It is efficient, i.e., runs in time polynomial with respect to the input size. (2) It returns an optimal solution. (3) It works for every instance of the…
