65 questions linked to/from How to prove greedy algorithm is correct
1 vote
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
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
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
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
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
450 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{... • 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) ... 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 ... 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

15 30 50 per page