Greedy Method for Task Scheduling Problems
The greedy method is a powerful algorithm design technique used in solving various optimization problems. In the context of task scheduling, we explore two specific problems: minimizing the number of machines needed to complete all tasks and maximizing the number of non-overlapping intervals on a single machine. By employing greedy strategies such as sorting tasks based on start or finish times and assigning tasks optimally, we can efficiently solve these scheduling challenges.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 16 More problems on the Greedy Method CS 161 Design and Analysis of Algorithms Ioannis Panageas
Greedy method The greedy method is a general algorithm design technique, in which given: configurations: different choices we need to make objective function: a score assigned to all configurations, which we want to either maximize or minimize We should make choices greedily: We can find a globally- optimal solution by a series of local improvements from a starting configuration. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 1: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform all the tasks using a minimum number of machines. A machine can serve one task at a given time. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 1: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform all the tasks using a minimum number of machines. A machine can serve one task at a given time. Idea: Sort tasks in increasing order of their start time. Assign first task to machine 1 and set ? = 1. When considering a new task, if all machines are busy, create a new machine, set ? = ? + 1 and assign the new task to the new machine otherwise assign the new task to an available machine. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 2: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform as many tasks as possible using one machine. In other words, find the maximum number of non-overlapping intervals. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 2: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform as many tasks as possible using one machine. In other words, find the maximum number of non-overlapping intervals. Idea: Sort tasks in increasing order of their finish time. Perform first task and remove all overlapping tasks with first task. Repeat the same process to the remaining tasks. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 2: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform as many tasks as possible using one machine. In other words, find the maximum number of non-overlapping intervals. Idea: Sort tasks in increasing order of their finish time. Perform first task and remove all overlapping tasks with first task. Repeat the same process to the remaining tasks. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 2: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform as many tasks as possible using one machine. In other words, find the maximum number of non-overlapping intervals. Idea: Sort tasks in increasing order of their finish time. Perform first task and remove all overlapping tasks with first task. Repeat the same process to the remaining tasks. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 2: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform as many tasks as possible using one machine. In other words, find the maximum number of non-overlapping intervals. Idea: Sort tasks in increasing order of their finish time. Perform first task and remove all overlapping tasks with first task. Repeat the same process to the remaining tasks. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 2: Given: a set ? of ? tasks, each having a start time ??and a finish time ?? (where ??< ??) Goal: Perform as many tasks as possible using one machine. In other words, find the maximum number of non-overlapping intervals. Idea: Sort tasks in increasing order of their finish time. Perform first task and remove all overlapping tasks with first task. Repeat the same process to the remaining tasks. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Idea: Sort tasks in decreasing order of their profit. Repeat the following until run out of tasks: Choose first task and schedule it at the latest time possible without exceeding deadline. If not possible, discard the task. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Idea: Sort tasks in decreasing order of their profit. Repeat the following until run out of tasks: Choose first task and schedule it at the latest time possible without exceeding deadline. If not possible, discard the task. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Idea: Sort tasks in decreasing order of their profit. Repeat the following until run out of tasks: Choose first task and schedule it at the latest time possible without exceeding deadline. If not possible, discard the task. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Idea: Sort tasks in decreasing order of their profit. Repeat the following until run out of tasks: Choose first task and schedule it at the latest time possible without exceeding deadline. If not possible, discard the task. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Idea: Sort tasks in decreasing order of their profit. Repeat the following until run out of tasks: Choose first task and schedule it at the latest time possible without exceeding deadline. If not possible, discard the task. Design and Analysis of Algorithms
Scheduling jobs/tasks Problem 3: You are given a set ? of ? tasks, each having a deadline time ?? and profit ?? if completed and needs one unit of time to be completed. You have only one machine. Goal: Complete non-overlapping tasks to maximize your profit. Idea: Sort tasks in decreasing order of their profit. Repeat the following until run out of tasks: Choose first task and schedule it at the latest time possible without exceeding deadline. If not possible, discard the task. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, a matching is a collection of edges that do not share a vertex. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, a matching is a collection of edges that do not share a vertex. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, a matching is a collection of edges that do not share a vertex. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, a matching is a collection of edges that do not share a vertex. Problem: Given a tree graph, compute/find a maximum matching. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, a matching is a collection of edges that do not share a vertex. Problem: Given a tree graph, compute/find a maximum matching. We know how to do it for bipartite graphs via maxflow!! Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, a matching is a collection of edges that do not share a vertex. Problem: Given a tree graph, compute/find a maximum matching. We know how to do it for bipartite graphs via maxflow!! Trees are bipartite! Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Question: The green edge has a leaf as an endpoint. Should it be in the matching? Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Maximum Matching on trees Problem: Given a tree graph, compute/find a maximum matching. Do not use Maxflow, but directly Greedy. Idea: Choose an edge with one endpoint being a leaf and put it in the matching. Remove all other incident edges. The new graph is a union of trees. Repeat until run out of edges. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, an independent set is a collection of vertices that do not share an edge. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, an independent set is a collection of vertices that do not share an edge. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, an independent set is a collection of vertices that do not share an edge. Design and Analysis of Algorithms
Problems on trees using Greedy Definition: Given a graph ?, an independent set is a collection of vertices that do not share an edge. Problem: Given a tree graph, compute/find a maximum independent set. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Question: Should a leaf be part of the independent set? Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
Maximum Independent set on trees Problem: Given a tree graph, compute/find a maximum independent set. Idea: Choose a leaf (or isolated vertex) and put it in the independent set. Remove the neighboring vertex (and incident edges). The new graph is a union of trees. Repeat until run out of vertices. Design and Analysis of Algorithms
