# Tag Info

### How to prove greedy algorithm is correct

Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a ...
• 143k

### How to prove greedy algorithm is correct

I will use the following simple sorting algorithm as an example: ...
• 5,910
Accepted

• 270k
Accepted

### Correctness of the greedy algorithm

If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions. But there is an 8 blocks solution (on the right). The problem with a ...
• 4,537

### A general algorithm for greedy algorithms

There is no such thing as the correct generalization of the greedy selection technique, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with ...
• 270k

### Please explain a greedy algorithm in a naive manner

Greedy algorithms can be used whenever you can think of the solution to the problem being reached in steps. The strategy is then just to choose the next step that looks best in some (usually simple, "...
• 13.7k

### Please explain a greedy algorithm in a naive manner

Your understanding is completely wrong: what you describe is known as hill climbing or gradient descent in the continuous case, and local search in the discrete case. The best way to understand what ...
• 270k

### Greedy and backtracking solutions to an arrangement problem with constraints

The idea of the backtracking algorithm is simple, though somewhat cumbersome to express. Perhaps it's easiest to explain it working through the example in the question. We start by putting $T_1$ on ...
• 270k

### Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use. There has been a recent line of work investigating algorithms for ...
Accepted

### set with maximum sum consisting of mutually co-prime numbers

Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating. Since the numbers are mutually co-...
• 25.5k
Accepted

### Vertex cover algorithms for directed graphs?

Thanks for the edit! This isn't vertex cover; it's something different. There are simple algorithms for this problem. Decompose the graph into a dag of strongly connected components. (The dag is ...
• 143k
Accepted

• 56
Accepted

### Maximum cut using a 1/2 approximation greedy algorithm

Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the ...
• 270k
Accepted

### Correctness proof for greedy algorithm based on ratio

The strategy to prove your ratio greedy algorithm is what I called "unimprovable solution by exchange of elements". Instead of proving that an algorithm produces the optimal solution, this strategy ...
• 34.8k
Keep all the values $\frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$. We would first like to update all ...