greedy algorithm task assignment

Greedy Algorithms Explained with Examples

What is a greedy algorithm?

You may have heard about a lot of algorithmic design techniques while sifting through some of the articles here. Some of them are:

• Brute Force
• Divide and Conquer
• Greedy Programming
• Dynamic Programming to name a few. In this article, you will learn about what a greedy algorithm is and how you can use this technique to solve a lot of programming problems that otherwise do not seem trivial.

Imagine you are going for hiking and your goal is to reach the highest peak possible. You already have the map before you start, but there are thousands of possible paths shown on the map. You are too lazy and simply don’t have the time to evaluate each of them. Screw the map! You started hiking with a simple strategy – be greedy and short-sighted. Just take paths that slope upwards the most. This seems like a good strategy for hiking. But is it always the best ?

After the trip ended and your whole body is sore and tired, you look at the hiking map for the first time. Oh my god! There’s a muddy river that I should’ve crossed, instead of keep walking upwards. This means that a greedy algorithm picks the best immediate choice and never reconsiders its choices. In terms of optimizing a solution, this simply means that the greedy solution will try and find local optimum solutions - which can be many - and might miss out on a global optimum solution.

Formal Definition

Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.

Greedy algorithms have some advantages and disadvantages:

• It is quite easy to come up with a greedy algorithm (or even multiple greedy algorithms) for a problem. Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer). For the Divide and conquer technique, it is not clear whether the technique is fast or slow. This is because at each level of recursion the size of gets smaller and the number of sub-problems increases.
• The difficult part is that for greedy algorithms you have to work much harder to understand correctness issues. Even with the correct algorithm, it is hard to prove why it is correct. Proving that a greedy algorithm is correct is more of an art than a science. It involves a lot of creativity. Usually, coming up with an algorithm might seem to be trivial, but proving that it is actually correct, is a whole different problem.

Interval Scheduling Problem

Let's dive into an interesting problem that you can encounter in almost any industry or any walk of life. Some instances of the problem are as follows:

• You are given a set of N schedules of lectures for a single day at a university. The schedule for a specific lecture is of the form (s time, f time) where s time represents the start time for that lecture and similarly the f time represents the finishing time. Given a list of N lecture schedules, we need to select maximum set of lectures to be held out during the day such that   none of the lectures overlap with one another i.e. if lecture Li and Lj are included in our selection then the start time of j >= finish time of i or vice versa .
• Your friend is working as a camp counselor, and he is in charge of organizing activities for a set of campers. One of his plans is the following mini-triathlon exercise: each contestant must swim 20 laps of a pool, then bike 10 miles, then run 3 miles.
• The plan is to send the contestants out in a staggered fashion, via the following rule: the contestants must use the pool one at a time. In other words, first one contestant swims the 20 laps, gets out, and starts biking.
• As soon as this first person is out of the pool, a second contestant begins swimming the 20 laps; as soon as he or she is out and starts biking, a third contestant begins swimming, and so on.
• Each contestant has a projected swimming time, a projected biking time, and a projected running time. Your friend wants to decide on a schedule for the triathlon: an order in which to sequence the starts of the contestants.
• Let's say that the completion time of a schedule is the earliest time at which all contestants will be finished with all three legs of the triathlon, assuming the time projections are accurate. What is the best order for sending people out, if one wants the whole competition to be over as soon as possible? More precisely, give an efficient algorithm that produces a schedule whose completion time is as small as possible

The Lecture Scheduling Problem

Let's look at the various approaches for solving this problem.

Earliest Start Time First  i.e. select the interval that has the earliest start time. Take a look at the following example that breaks this solution. This solution failed because there could be an interval that starts very early but that is very long. This means the next strategy that we could try would be where we look at smaller intervals first.

Smallest Interval First  i.e. you end up selecting the lectures in order of their overall interval which is nothing but their   finish time - start time . Again, this solution is not correct. Look at the following case.

You can clearly see that the shortest interval lecture is the one in the middle, but that is not the optimal solution here. Let's look at yet another solution for this problem deriving insights from this solution.

Least Conflicting Interval First  i.e. you should look at intervals that cause the least number of conflicts. Yet again we have an example where this approach fails to find an optimal solution.

The diagram shows us that the least confliciting interval is the one in the middle with just 2 conflicts. After that we can only pick the two intervals at the very ends with conflicts 3 each. But the optimal solution is to pick the 4 intervals on the topmost level.

Earliest Finishing time first . This is the approach that always gives us the most optimal solution to this problem. We derived a lot of insights from previous approaches and finally came upon this approach. We sort the intervals according to increasing order of their finishing times and then we start selecting intervals from the very beginning. Look at the following pseudo code for more clarity.

When do we use Greedy Algorithms

Greedy Algorithms can help you find solutions to a lot of seemingly tough problems. The only problem with them is that you might come up with the correct solution but you might not be able to verify if its the correct one. All the greedy problems share a common property that a local optima can eventually lead to a global minima without reconsidering the set of choices already considered.

Greedy Algorithms help us solve a lot of different kinds of problems, like:

Shortest Path Problem:

Minimum Spanning Tree Problem in a Graph

Huffman Encoding Problem

K Centers Problem

If this article was helpful, share it .

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

Learn Python practically and Get Certified .

Popular Tutorials

Popular examples, reference materials, learn python interactively, dsa introduction.

• What is an algorithm?
• Data Structure and Types
• Why learn DSA?
• Asymptotic Notations
• Master Theorem
• Divide and Conquer Algorithm

Data Structures (I)

• Types of Queue
• Circular Queue
• Priority Queue

Data Structures (II)

• Linked List
• Linked List Operations
• Types of Linked List
• Heap Data Structure
• Fibonacci Heap
• Decrease Key and Delete Node Operations on a Fibonacci Heap

Tree based DSA (I)

• Tree Data Structure
• Tree Traversal
• Binary Tree
• Full Binary Tree
• Perfect Binary Tree
• Complete Binary Tree
• Balanced Binary Tree
• Binary Search Tree

Tree based DSA (II)

• Insertion in a B-tree
• Deletion from a B-tree
• Insertion on a B+ Tree
• Deletion from a B+ Tree
• Red-Black Tree
• Red-Black Tree Insertion
• Red-Black Tree Deletion

Graph based DSA

• Graph Data Structure
• Spanning Tree
• Strongly Connected Components
• Adjacency Matrix
• Adjacency List
• DFS Algorithm
• Breadth-first Search
• Bellman Ford's Algorithm

Sorting and Searching Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Counting Sort
• Bucket Sort
• Linear Search
• Binary Search

Greedy Algorithms

• Greedy Algorithm
• Ford-Fulkerson Algorithm
• Dijkstra's Algorithm

Kruskal's Algorithm

Prim's Algorithm

• Huffman Coding

Dynamic Programming

• Floyd-Warshall Algorithm
• Longest Common Sequence

Other Algorithms

Backtracking Algorithm

• Rabin-Karp Algorithm

DSA Tutorials

• What is an Algorithm?

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result.

The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top-down approach.

This algorithm may not produce the best result for all the problems. It's because it always goes for the local best choice to produce the global best result.

However, we can determine if the algorithm can be used with any problem if the problem has the following properties:

1. Greedy Choice Property

If an optimal solution to the problem can be found by choosing the best choice at each step without reconsidering the previous steps once chosen, the problem can be solved using a greedy approach. This property is called greedy choice property.

2. Optimal Substructure

If the optimal overall solution to the problem corresponds to the optimal solution to its subproblems, then the problem can be solved using a greedy approach. This property is called optimal substructure.

• Advantages of Greedy Approach
• The algorithm is easier to describe .
• This algorithm can perform better than other algorithms (but, not in all cases).
• Drawback of Greedy Approach

As mentioned earlier, the greedy algorithm doesn't always produce the optimal solution. This is the major disadvantage of the algorithm

For example, suppose we want to find the longest path in the graph below from root to leaf. Let's use the greedy algorithm here.

Greedy Approach

1. Let's start with the root node 20 . The weight of the right child is 3 and the weight of the left child is 2 .

2. Our problem is to find the largest path. And, the optimal solution at the moment is 3 . So, the greedy algorithm will choose 3 .

3. Finally the weight of an only child of 3 is 1 . This gives us our final result 20 + 3 + 1 = 24 .

However, it is not the optimal solution. There is another path that carries more weight ( 20 + 2 + 10 = 32 ) as shown in the image below.

Therefore, greedy algorithms do not always give an optimal/feasible solution.

• To begin with, the solution set (containing answers) is empty.
• At each step, an item is added to the solution set until a solution is reached.
• If the solution set is feasible, the current item is kept.
• Else, the item is rejected and never considered again.

Let's now use this algorithm to solve a problem.

• Example - Greedy Approach
• Create an empty solution-set = { } . Available coins are {5, 2, 1} .
• We are supposed to find the sum = 18 . Let's start with sum = 0 .
• Always select the coin with the largest value (i.e. 5) until the sum > 18 . (When we select the largest value at each step, we hope to reach the destination faster. This concept is called greedy choice property .)
• In the first iteration, solution-set = {5} and sum = 5 .
• In the second iteration, solution-set = {5, 5} and sum = 10 .
• In the third iteration, solution-set = {5, 5, 5} and sum = 15 .
• In the fourth iteration, solution-set = {5, 5, 5, 2} and sum = 17 . (We cannot select 5 here because if we do so, sum = 20 which is greater than 18. So, we select the 2nd largest item which is 2.)
• Similarly, in the fifth iteration, select 1. Now sum = 18 and solution-set = {5, 5, 5, 2, 1} .
• Different Types of Greedy Algorithm
• Knapsack Problem
• Minimum Spanning Tree
• Single-Source Shortest Path Problem
• Job Scheduling Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm

Table of Contents

Sorry about that.

Related Tutorials

DS & Algorithms

ThinkIR: The University of Louisville's Institutional Repository

Home > ETD > 369

Electronic Theses and Dissertations

A modified greedy algorithm for the task assignment problem..

Allison M. Douglas , University of Louisville

Date on Master's Thesis/Doctoral Dissertation

Document type.

Master's Thesis

Degree Name

Industrial Engineering

Committee Chair

Depuy, Gail W.

Production management; Personnel management--Data processing

Assigning workers to tasks in an efficient and cost effective manner is a problem that nearly every company faces. This task assignment problem can be very time consuming to solve optimally. This difficulty increases as problem size increases. Most companies are large enough that it isn't feasible to find an optimal assignment; therefore a good heuristic method is needed. This project involved creating a new heuristic to solve this problem by combining the Greedy Algorithm with the Meta-RaPS method. The Greedy Algorithm is a near-sighted assignment procedure that chooses the best assignment at each step until a full solution is found. Although the Greedy Algorithm finds a good solution for small to medium sized problems, introducing randomness using the meta-heuristic Meta-RaPS results in a better solution. The new heuristic runs 5000 iterations and reports the best solution. The final Excel® VBA program solves a small sized problem in less than one minute, and is within 10% of the optimal solution, making it a good alternative to time consuming manual assignments. Although larger, more realistic problems will take longer to solve, good solutions will be available in a fraction of the time compared to solving them optimally.

Recommended Citation

Douglas, Allison M., "A modified greedy algorithm for the task assignment problem." (2007). Electronic Theses and Dissertations. Paper 369. https://doi.org/10.18297/etd/369

Since February 12, 2015

Advanced Search

• Notify me via email or RSS
• Collections
• Disciplines

Author Corner

• Collection Policy
• License Agreements
• ThinkIR Electronic Resource Guide
• Submit Research

Related Links

• Guidelines for the Preparation and Processing of Theses and Dissertations (School of Interdisciplinary & Graduate Studies) ( PDF )
• University of Louisville Libraries Research Assistance and Instruction
• Nonexclusive License to Electronically Disseminate UofL ETD ( PDF )
• Data Management Guides for Theses and Dissertations

Home | About | FAQ | My Account | Accessibility Statement

Privacy Copyright

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Simple Task-Assignment Problem

I have this simple 'assignment' problem:

We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike the general assignment formulation in Wikipedia, a task $t_c$ can only be assigned to an agent based on the task's preferred agents $ta_c \subseteq A$. For example, if we have $ta_1= \{a_1, a_3\}$, that means that task $t_1$ can only be assigned to either agents $a_1$ or $a_3$. Now, each agent $t_d$ has a quota $q_d$ where $q_d$ is positive integer. This means that $a_d$ must be assigned with $q_d$ number of tasks.

The Problem

Given above and a set of quota $\{q_1, q_2, \dotso, q_n\}$, is there an assignment of tasks to agents such that all agents meet their respective quota $q$. Note that it is not necessarily that all tasks be assigned to an agent.

Possible Solution

I have tried reformulating this problem in terms of a bipartite graph $G(A, T, E = \cup ta_c)$ and expressed as a form of matching problem where given a matching $M$, a vertex agent $a_d\in A$ is matched up to $q_d$ times or is incident to $q_d$ edges in $M$ but the vertices in $T$ is incident to only one edge in $M$. Not really like the usual matching problem which requires that the edges in $M$ are pairwise non-adjacent.

However, it was suggested by someone (from cstheory, he knows who he is) that I could actually work this out as a maximum matching problem, by replicating an agent $a_d$ into $q_d$ vertices and 'conceptually' treat them as different vertices as input to the matching algorithm. The set of edges $E$ is also modified accordingly. Call the modified graph as $G'$

It is possible to have more than 1 maximum matchings from graph $G'$. Now, if I understand this correctly, I still have to check each of the resulting maximum matchings and see that at least one of them satisfies the $qouta$ constraint of each $agent$ to actually provide the solution to the problem.

Now, I want to prove that not finding one maximum matching $M$ $\in$ set of all maximum matchings of the graph $G'$ that satisfies the $qouta$ constraint of the problem guarantees that there really exists no solution to the problem instance, otherwise a solution exist which is $M$.

I want to show that this algorithm always give correct result.

Can you share to me some intuition on how I might go to show this?

• proof-techniques
• assignment-problem

As I stated on the CSTheory post, this is solved via maximum matching. The following should give enough intuition to show that each agent $a_i$ has a $q_i$-matching iff a transformed graph $G'$ has a matching. First, construct the graph $G$. Now, for each agent $a_i$ and quota $q_i$, make a new graph $G'$ that has $q_i$ copies of $a_i$. That is to say, if agent $a_i$ has quota $q_i = 3$, make 2 new nodes $a_i', a_i''$ that have the same tasks as $a_0$.

Here is an illustration to help. Supposed we have the complete bipartite graph $K_{2,3}$ where agent $q_1 = 2, q_2 = 1$.

Original graph $G$, and modified graph $G'$:

We see that agent $a_1$ has two copies in the new graph $G'$, while agent $a_2$ maintains just his lone copy. Solving for the maximum matching in $G'$ and then merging all copies of an agent to the original and you will have your best possible assignment. Since the edges are unweighted, one possible solution is (and merged solution):

• $\begingroup$ hi again nicholas. Thank you for the suggestion! But I'm past that, and I'm asking a different question now. :) As I understand my problem, a maximum matching of $G$ is only a possible solution to it. I still have to check that a maximum matching satisfies the $qouta$ constraint of the problem. I hope this requirement of the problem looks clear to you. It's more of a decision problem, which asks whether a matching $M$ exists on $G$ such that each $a_d\in A$ (or in your suggested formulation, all vertex $a_d$ copies)is incident on a edge in $M$. $\endgroup$ –  ultrajohn Commented Sep 22, 2012 at 23:48
• 1 $\begingroup$ I understand. Start by proving that if $G'$ has a matching, then quota is satisfied. Then prove if quota is satisfied then there exists a matching in $G'$. All the transformation-work has been done. Use that as the logical foundation. $\endgroup$ –  Nicholas Mancuso Commented Sep 22, 2012 at 23:52
• $\begingroup$ So if you remember, you answered a question I posted earlier about size of the maximum matching $M$ of $G'$. You said, that $|M|$ is not necessarily equal to $\min(|A|,|T|)$. For my problem, a solution exists if and only if a maximum matching M exists such that $|M| = \sum_{i=1}^{n} q_i$. Oh I think I just found out the answer to my question. :) $\endgroup$ –  ultrajohn Commented Sep 22, 2012 at 23:53
• 1 $\begingroup$ Yes, but remember $M$ must be in $G'$, not in $G$. $\endgroup$ –  Nicholas Mancuso Commented Sep 22, 2012 at 23:54
• $\begingroup$ Yes, sorry for the mixed up. I think i know how to prove that now. Thank you really! $\endgroup$ –  ultrajohn Commented Sep 22, 2012 at 23:57

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged algorithms graphs proof-techniques assignment-problem or ask your own question .

• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Announcing a change to the data-dump process

Hot Network Questions

• Are there non-religious variants of moral realism that defend the existence of objectively evil thoughts, intentions, and desires?
• Ubuntu 24.04 LTS Repositories what is the difference between noble vs noble-updates vs noble-security vs noble-backports
• Are there any signs that the laptop fan is broken during use?
• Jurisdiction: Can police officers open mail addressed to a stranger?
• How does the grammar in 这不关你的事 work?
• How is the name "Took" pronounced?
• Possibly manipulated recommendation letter - inform alleged author?
• Is the "assemble" a transitive or intransitive verb in "The shelves are easy to assemble"?
• Could Swashplate be replaced with small electric motors?
• How will a very short undergrad impact PhD applications?
• Why are there no 12V/5A USB PD chargers/batteries?
• How does Wild Shape interact with the clone spell?
• Five numbers with median and mean
• Is this an ordinary workplace experience for an intern?
• How can DC charge a capacitor?
• Do strawberry seeds have different DNA within the same fruit?
• How long should I boil a liquid mixture containing vanilla extract to vaporize the alcohol, when making ice cream?
• Applications take a few seconds to open, but only the first time I open them
• In an expanding universe could black hole pairs keep orbiting each other forever?
• A movie maybe from the 70’s about people being turned to dust out in the sunlight
• Child's teddies "being mean" after dark
• Negotiating contractor salary?
• How were East German citizens who defected to West Berlin able to travel to the rest of West Germany? (If at all)
• Do some chemicals degrade at low temperatures?

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

Complexity of a greedy assignment algorithm

The assignment problem asks to find a set of n elements with maximal possible sum in distinct rows and columns of a given n-by-n matrix. It can be solved optimally by the Hungarian algorithm in O(n^3). However, let us consider the following suboptimal greedy algorithm:

• Choose the maximal element in the remaining matrix
• Add this element to the resulting set, i.e. match the row of this element to its column, and remove these row and column from the matrix
• Repeat from the step 1.

What would be an efficient data structure to implement such an algorithm? Can its time complexity be O(n^2), if it requires O(n^2 log(n)) only to sort all the elements?

• time-complexity
• mathematical-optimization

• O(n^2) is fairly straightforward, but what's the point? –  Amit Commented Mar 17, 2016 at 22:20
• The point is to reduce the complexity by sacrificing optimality, but how do you do this in O(n^2)? –  xivaxy Commented Mar 17, 2016 at 22:26
• Sorry I misunderstood you the first time. You want your algorithm in O(n^2) including the loop (step 3), right? –  Amit Commented Mar 17, 2016 at 22:33
• Right, I want to find all these n elements with possibly maximal sum. –  xivaxy Commented Mar 17, 2016 at 22:36

2 Answers 2

A complexity of O(n 2 logn) may be achieved using something as follows.

You initially store a sorted version of each of n rows and columns.(the exact structure this stored rows and columns will use is clarified later in this answer) Note that, even though you will sort these according to the values of the cells, the values of the cells should be stored alongside their initial indices. The initial indices will help when deleting rows and columns. (step 2 of your algorithm)

After the preprocessing mentioned above, have a loop that iterates n times. Inside this loop will be the steps of your algorithm. At each iteration;

Step 1: Check the largest elements in each sorted row and column, updating the value and address for the globally maximal element.

Step 2.1: Add element to the resulting array/list/etc, and remove it from the sorted row and column structure of the corresponding row and column.

Step 2.2: Traverse each sorted row structure. For each row, we need to delete a column. Since we have the matrix and the address of the maximal element, we can also access the exact value and address of the column we are deleting for each row. Utilizing this, in each sorted row structure, given it is sorted, conduct a binary search to find that element, and remove it.

Here is the thing! If you store this sorted row structure as a straightforward array, removing this element will take O(n) time, as you have to carry the remaining part of the array to the left by 1. A solution I can think of is to use a structure akin to STL's set . It can, in fact, find in O(logn) just like binary search, and provides O(logn) time insertion and deletion.

Step 2.3: Identical to Step 2.2, this time each column structure is traversed. As we are deleting a row, we are removing an element from each column. However, thanks to having found the address(i.e. row&column) and the value of the globally maximal element, we know which row we are removing and the value and address of the element we remove from each column. So, for each column structure we find and remove that element from the STL's set-like data structure storing the sorted version of that column.

Performance

Preprocessing: Now that we know what kind of a data structure stores sorted rows and columns, we can say that it takes O(n 2 logn) as there are 2n of those structures, and we insert n elements to each one of them in O(logn) time.

Step 1: There are 2n sorted structures, which means accessing their largest element in O(logn) time will have a combined O(nlogn) time complexity.

Step 2.1: Though it depends on the data structure the resulting data is kept in, assuming it is an array, it takes O(1) time to add an element to it. However this step has an overall complexity of O(logn) as we need to remove the maximal element from the sorted row and column structures it belongs to.

Step 2.2: There are n sorted row structures for which we do a find and remove operation, causing an O(nlogn) burden.

Step 2.3: Has O(nlogn) cost, same as Step 2.2.

Considering steps 2.1, 2.2, and 2.3 are done n times, the overall complexity of the algorithm is O(n 2 logn) .

Implementation

Below you may find a complete implementation of the algorithm I mentioned above, which seems to be working. The gist of the algorithm is the same, with minor changes due to implementation like defining a negative infinity or using an extra bool vector to store whether a row or column is completely deleted.(i.e. we won't bother to look at its sorted structure when looking for the maximal element in remaining matrix)

Once the elements are sorted, you can just scan through, using two arrays to track the deleted rows and columns. In untested Python:

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged algorithm time-complexity mathematical-optimization or ask your own question .

• Featured on Meta
• Announcing a change to the data-dump process
• We've made changes to our Terms of Service & Privacy Policy - July 2024

Hot Network Questions

• Asymptotics of sum involving square roots
• Does GDPR's "Legitimate Interest" allow spam?
• How is the name "Took" pronounced?
• ^ symbol in music theory
• Could Swashplate be replaced with small electric motors?
• Wife missing in Italy
• Is it safe to keep an outdated credit card?
• how to text non apple users on my MacBook Air?
• Thomson's lamp: a useless paradox?
• How to make an operator form of Part[] to use with // (Postfix)
• Can multi-threading improve performance of an IO-bound process?
• Can an exponentially growing population perform eugenics and selective breeding at short time scales?
• Is it a good practice to share a certificate between two applications
• How will a very short undergrad impact PhD applications?
• What might be causing ls to ignore LS_COLORS for setgid (sg, g+s) directories?
• Compact rotatable connection that supports pull forces?
• What is the difference of "limiting reactant" and "limiting reagent"?
• What is the timescale for "$ Change" and "% Change" on Vanguard's Holdings page?
• Thermal printer head made out of PCB
• Why is this not definitionally held?
• How to convert digital value from MEMS microphone to Pa
• Why does modified z-score not pick up an obvious outlier?
• How to remove the circled numbers from the image and obtain an image without circled numbers?
• Efficient way to remove nailed-down plywood flooring in attic without damaging it?

• Analysis of Algorithms
• Backtracking
• Dynamic Programming
• Divide and Conquer
• Geometric Algorithms
• Mathematical Algorithms
• Pattern Searching
• Bitwise Algorithms
• Branch & Bound
• Randomized Algorithms

Scheduling in Greedy Algorithms

In this article, we will discuss various scheduling algorithms for Greedy Algorithms . Many scheduling problems can be solved using greedy algorithms.

Problem statement: Given N events with their starting and ending times, find a schedule that includes as many events as possible. It is not possible to select an event partially. Consider the below events:

• In this case, the maximum number of events is two. As selected events B and D are as follows:

• It is possible to invent several greedy algorithms for the problem.

Algorithms that work with every case:

Algorithm 1 : 

• The first idea is to select as short events as possible. In the example, this algorithm selects the following events:

• However, selecting short events is not always a correct strategy. For example, the algorithm fails in the below case:

• If short event is selected, it can only select one event. However, it would be possible to select both long events.

Algorithm 2 :

• Another idea is to always select the next possible event that begins as early as possible. This algorithm selects the following events:

• However, given a counter example for this algorithm. In this case, the algorithm only selects one event:

• If the first event is selected, it is not possible to select any other events. However, it would be possible to select the other two events.

Algorithm 3 :

• The third idea is to always select the next possible event that ends as early as possible. This algorithm selects the following events:

• It turns out that this algorithm always produces an optimal solution.
• The reason for this is that it is always an optimal choice to first select an event that ends as early as possible.
• After this, it is an optimal choice to select the next event using the same strategy, etc., until any other event can’t be selected.
• One way the algorithm works is to consider what happens if first select an event that ends later than the event that ends as early as possible.
• Now, with having at most an equal number of choices how the next event can be selected.
• Hence, selecting an event that ends later can never yield a better solution, and the greedy algorithm is correct.

Please Login to comment...

Similar reads.

• Advanced Data Structure
• Operating Systems Questions
• cpu-scheduling
• Operating Systems-CPU Scheduling

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Optimizing Job Assignments with Python: A Greedy Approach

In this article, we will learn the skill of job assignment which is a very important topic in the field of Operations Research. For this, we will utilize Python programming language and the Numpy library for the same. We will also solve a small case on a job assignment.

Job assignment involves allocating tasks to workers while minimizing overall completion time or cost. Python’s greedy algorithm, combined with NumPy, can solve such problems by iteratively assigning jobs based on worker skills and constraints, enabling efficient resource management in various industries.

Recommended: Maximizing Cost Savings Through Offshore Development: A Comprehensive Guide

Recommended: Delivery Route Optimization using Python: A Step-by-Step Guide

What is a Job Assignment?

Let us understand what a job assignment is with an example. In our example, three tasks have to be completed. Three workers have different sets of skills and take different amounts of time to complete the above-mentioned tasks. Now our goal is to assign the jobs to the workers to minimize the period of completing the three tasks.

Now, we solve the above problem using the concepts of Linear programming. Now there are certain constraints as well, each worker can be assigned only a single job at a time. Our objective function is the sum of all the time taken by the workers and minimize it. Let us now solve this problem using the power of the Numpy library of Python programming language.

Let us now look at the output of the problem.

From the output, we can see that The assignment is complete and optimized. Let us now look at a small case and understand the job assignment further.

A Real-World Job Assignment Scenario

Continuing with the example of assigning workers some jobs, in this case, a company is looking to get some work done with the help of some freelancers. There are 15 jobs and we have 10 freelancers. We have to assign jobs to workers in such a way, that we minimize the time as well as the cost of the whole operation. Let us now model this in the Python programming language.

This problem is solved using the greedy algorithm. In short, the greedy algorithm selects the most optimal choice available and does not consider what will happen in the future while making this choice. In the above code, we have randomly generated data on freelancer details. Let us now look at the output of the code.

Thus, we complete our agenda of job assignment while minimizing costs as evidenced by the output.

Assigning jobs optimally is crucial for maximizing productivity and minimizing costs in today’s competitive landscape. Python’s powerful libraries like NumPy make it easy to implement greedy algorithms and solve complex job assignment problems, even with larger sets of jobs and workers. How could you adapt this approach to accommodate dynamic changes in job requirements or worker availability?

Recommended: Splitting Lists into Sub-Lists in Python: Techniques and Advantages

Recommended: Object Detection with OpenCV: A Step-by-Step Tutorial

Group computing task assignment and association analysis based on big data technology

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options, recommendations, research on the impact of big data technology on management accounting.

As the application of big data technology continues to expand. The rational use of big data technology in management accounting. Big data technology makes accounting work efficiency significantly improved. Big data technology has promoted the reform and ...

A Comprehensive Overview of BIG DATA Technologies: A Survey

In as much as the approaches of the new revolution, machines including transmission media like social media sites, nowadays quantity of data swell hastily. So, size is the core and only facet that leaps the mention of BIG DATA. In this article, an ...

Research on the application of cloud computing technology in computer big data analysis

With the development of the times, computer technology is making continuous progress. People's every move is generating data. In the face of such a large amount of data information, the traditional data processing technology has been unable to meet ...

Information

Published in.

Inderscience Publishers

Geneva 15, Switzerland

Publication History

Author tags.

• big data technology
• group computing
• task assignment
• association analysis
• self-processing algorithm
• Research-article

Contributors

Other metrics, bibliometrics, article metrics.

• 0 Total Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.