We know that the Greedy Approach in general, picks an element from a set of candidate elements that satisfies a predefined criteria (selection function) and is added to the solution if it satisfies the constraint (feasibility function).

My question is can there be an optimization problems where there is no constraint and hence no feasibility function which means we just have the (greedy) selection criteria that we blindly keep following and applying on the candidate set of elements, keep building the solution and at one point arrive at a solution? The motivation behind the question is explained below.

I saw quite a few examples of Greedy Approach:

  • Knapsack - constraint is the capacity of the bag
  • job sequencing with deadlines - constraint is each job has its own deadline
  • Optimal Merge Pattern - constraint is that you cannot merge than 2 lists at a time?
  • Minimum cost spanning tree (Prim's and Kruskal's algorithm) - constraint is that the result should be a "spanning" tree => no. of edges should be one less than the no. of vertices?
  • Dijskstra's algorithm - what is the constraint here?

I have listed only the Optimization problems using Greedy approach that I am familiar with. Apart from this list, are there other optimization problems without constraints?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.