# Questions tagged [greedy-algorithms]

Questions about algorithms that make at each step the locally optimal choice.

342 questions
Filter by
Sorted by
Tagged with
344 views

### Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
840 views

### GSAT incompleteness example

The GSAT (Greedy Satisfiability) algorithm can be used to find a solution to a search problem encoded in CNF. I'm aware that since GSAT is greedy, it is incomplete (which means there would be cases ...
582 views

### Finding an instance of an n-element set cover

Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter ...
1k views

### Solving a variant of interval scheduling problem [duplicate]

I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have a ...
1k views

### “Flow layouts” inside a GUI — how do I come up with a good algorithm?

I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode): ...
12 views

### Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment. Say that ...
87 views

92 views

### Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks

Lets just say I have two lists of the running time of tasks A and B. Formally, I would have: A = {a_1, a_2, a_3 ... a_n} B = {b_1, b_2, b_3 ... b_n} I can only ...
180 views

### How to restore diagonal-symmetric matrix that has been shuffled?

I have a square matrix M, which originally looked like this: 133 199 101 121 142 133 199 101 156 142 133 199 108 156 142 133 (so symmetric around the diagonal). ...
65 views

673 views

### Other greedy choices to solve activity selection problem

I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities. But surely ...
600 views

### Correctness of the greedy algorithm

I am trying to solve the following problem: Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of ...
3k views

### Vertex cover algorithms for directed graphs?

I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph. Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a ...
275 views

### Can sampling remove the limitations in greedy algorithm?

Given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or some structured manner reduce or remove the limitations of ...
667 views

### Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
88 views

I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms ...
360 views

### Find the coins required which sum to S

Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once). I was recently studying ...
Problem The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...