31 questions linked to/from How to prove greedy algorithm is correct
108 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. ...
4k 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 ...
740 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$ ...
907 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 ...
1k 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) ...
821 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 ...
138 views

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{... 1answer 475 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 ... 1answer 592 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. ... 1answer 295 views ### Minimal date interval cover algorithm The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. ... 1answer 450 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 ... 1answer 199 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 ... 0answers 313 views ### With restrictions, can the knapsack puzzle be solved with a greedy algorithm? I know that with the knapsack problem in general, there is no known greedy algorithm to solve it. But, say we add the following constraints: • All items have values equal to their weights (for all$...
I have this problem where I need to design a greedy algorithm. The problem is as follows: A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply \$...