Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
319
questions
1
vote
1answer
12k views
Proving greedy choice property of fractional knapsack
A typical way of proving the greedy choice property of the fractional knapsack problem is as follows:
From Slide 5 of this link:
Given: A set of items $I = \{I_1,I_2..I_n\}$ with weights $\{w_1,w_2 ....
14
votes
2answers
13k views
Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree
There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.
For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
For each ...
2
votes
1answer
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 ...
4
votes
1answer
577 views
Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible 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 ...
3
votes
3answers
8k views
Fractional Knapsack in linear time
How to solve fractional knapsack in linear time? I found this on Google but don't really understand it.
Choose element $r$ at random from $R$ (set of profit/weight ratios)
Determine
$R_1 = \{ p_i / ...
8
votes
4answers
9k views
Find non-overlapping scheduled jobs with maximum cost
Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum.
Now I'm not sure if a greedy algorithm will do the trick. That is, sort by ...
4
votes
1answer
310 views
Single machine job scheduling to minimize weighted sum of completion time
Given $n$ jobs, schedule them such that the weighted sum is minimum.
weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :
$S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
2
votes
2answers
3k views
Greedy Optimum Dominating Set For A Tree
I am trying to figure out a greedy algorithm that finds the optimum (minimum) dominating set for any tree in linear time.
So a greedy algorithm to find a dominating set for a general graph is not ...
3
votes
1answer
138 views
Show that approximation ratio for a convex hull algorithm is $\pi/2$
Facts: n points in the plane, each has one of k colors, all k colors are represented.
Problem: You wish to select k points, one of each color, such that the perimeter of the convex hull is as small ...
9
votes
1answer
210 views
Fixed-length decision-tree-like feature selection to minimize average search performance
I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear ...
0
votes
1answer
2k views
Greedy algorithms tutorial
Could anyone point me to simple tutorial on greedy algorithm for Minimum Spanning tree - Kruskal's and Prims' Method
I am looking for a tutorial which
does not include all the mathematical ...
29
votes
1answer
29k views
When can a greedy algorithm solve the coin change problem?
Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v.
E.g. for the coinset 1,5,10,20 this gives 2 ...
4
votes
1answer
531 views
Why do the swap step in Prim's algorithm for minimum spanning trees?
I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees.
Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
7
votes
1answer
922 views
Greedy choice and matroids (greedoids)
As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I ...
7
votes
2answers
523 views
Balanced weighting of edges in cactus graph
Given a cactus, we want to weight its edges in such a way that
For each vertex, the sum of the weights of edges incident to the vertex is no more than 1.
The sum of all edge weights is maximized.
...
2
votes
2answers
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):
...
1
vote
0answers
50 views
How to use greedy algorithm to solve this? [duplicate]
Possible Duplicate:
How to use greedy algorithm to solve this?
You are given $n$ integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ ...
21
votes
4answers
1k views
How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?
You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-...
23
votes
1answer
1k views
How fundamental are matroids and greedoids in algorithm design?
Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy ...
