Linked Questions
65 questions linked to/from How to prove greedy algorithm is correct
1
vote
0
answers
176
views
how to prove correctness of this greedy algorithm? [duplicate]
I did exercise problem from Pittsburgh university cs department.
homework.
Question 8 is somewhat exciting. Q8 is solved using greedy algorithm but I have no idea how to prove. Below is Question.
...
- 11
4
votes
1
answer
9k
views
How does "Greedy Stays Ahead" Prove an Optimal Greedy Algorithm?
I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem.
On the second page of Cornell's Greedy Stays ...
- 177
0
votes
3
answers
1k
views
Find longest path in graph with N nodes and N edges
We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ ...
- 1,418
0
votes
1
answer
3k
views
Is my proof of my greedy algorithm to find subsequence correct?
Credit to KleinBerg and Taros Book
Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
1
vote
1
answer
2k
views
Does a greedy strategy exist for this instance of the Bin Packing Problem?
I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 ...
- 13
4
votes
4
answers
450
views
How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?
For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
- 233
1
vote
1
answer
1k
views
Proof of a greedy algorithm concerning “Buy and Resell Problem”
"Buy and Resell Problem" can be described in the following way:
There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from ...
- 296
2
votes
0
answers
2k
views
Why is it necessary to sort according to the starting time in the interval partitioning problem?
What is the problem if we sort the intervals according to their finishing time like the interval scheduling problem? Could someone give a counterexample
?
Note- (refer here for detailed definition)
...
- 39
3
votes
1
answer
979
views
Using a greedy algorithm to find a cut S which at least half of the edges cut
Let $G$ be an undirected graph.
Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.
I tried to think about something like choosing the vertex with the highest degree, ...
- 133
0
votes
3
answers
2k
views
Optimality of a Greedy Algorithm
If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you ...
- 131
1
vote
3
answers
1k
views
How can I prove that my greedy algorithm for least guards is optimal?
This is the problem:
An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
- 251
2
votes
2
answers
596
views
Select a subset of k intervals which form maximum length if we take union of these k intervals
Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals.
Note that there are 2 cases ...
- 123
3
votes
1
answer
1k
views
How to prove a greedy algorithm that uses the longest increasing subsequence?
Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...
- 139
0
votes
1
answer
1k
views
Vertex Cover special cases
This was from a test from my university:
Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum ...
- 3
1
vote
2
answers
599
views
Why this greedy algorithm does not return the optimal solution to this NP-hard problem?
Problem:
In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective ...
- 1,046