Examples

The following examples illustrate some problems that can be solved with this approach:

1. Loading maximum containers in a cargo: For the given containers and the cargo having a capacity of 90kg90\\text{kg}90kg, fill the cargo with maximum containers without exceeding the capacity.
2. Graph coloring: Color a graph so that no two adjacent vertices are colored using the same color and minimum colors are used.

Real-world problems

Many problems in the real world use the greedy techniques pattern. Let’s look at some examples.

• CPU scheduling algorithms: In operating systems, managing how processes are assigned to the CPU for execution is critical for efficiency and performance. Greedy algorithms are used in CPU scheduling to decide the order of tasks based on specific criteria, such as minimizing waiting time, maximizing utilization, or ensuring fairness among users. By making greedy choices, such as selecting the process with the shortest expected completion time next (Shortest Job Next), systems aim to optimize overall throughput and resource utilization.
• Network Design in LANs: For large Local Area Networks (LANs) connecting numerous devices, efficient data transmission is vital. Greedy algorithms help in designing the network’s infrastructure to ensure data packets travel in the most efficient way possible. By finding a Minimum Spanning Tree (MST) for the network, a greedy algorithm like Prim’s or Kruskal’s ensures that all switches are connected with the least total cable length, reducing costs and improving network performance. This approach ensures minimal data transmission times and reduced chances of bottlenecks.
• Friend recommendations on social networking websites: Social networking platforms like Facebook, LinkedIn, and X (formerly Twitter) enhance user engagement by suggesting new friends or connections. A key algorithm behind this feature is Dijkstra’s algorithm, a greedy technique used to find the shortest paths between nodes in a graph. In this context, nodes represent users, and edges represent connections between them (like friendships). By finding the shortest path of connections between users, the algorithm can suggest people we may know or should connect with, based on your existing network of friends. This makes the platform more engaging by encouraging the growth of our social network through relevant connections.

Does your problem match this pattern?

• Yes, if both of these conditions are fulfilled:
  • Optimization problem: The problem is an optimization problem, where we are looking to find the best solution under a given set of constraints. This could involve minimizing or maximizing some value, such as cost, distance, time, or profit.
  • Making local choices leads to a global solution: The problem can be solved by making simple decisions based on the current option or state without needing to look ahead or consider many future possibilities.
• No, if any of these conditions is fulfilled:
  • Local choices lead to sub-optimal solutions: Our analysis shows that making local greedy choices leads us to a sub-optimal solution.
  • Problem lacks clear local optima: If the problem doesn’t naturally break down into a series of choices where we can identify the best option at each step, a greedy algorithm might not be applicable.

Prims