36 votes

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 ...
user avatar
  • 143k
14 votes

How to prove greedy algorithm is correct

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

Matrix Chain Multiplication Greedy Approach

You don't state why you think that your algorithm is correct. In fact, it is incorrect. Here is an example. Consider the problem of computing the product of matrices of dimensions $2\times 1$, $1\...
user avatar
8 votes
Accepted

Counterexample to this modified Dijkstra's

Your algorithm makes the wrong choice between the following two paths: 5 channels with a reliability of 50% (combined reliability 3.125%), weight $5 \cdot {1 \over 0.50} = 10$. A single channel with ...
user avatar
  • 12.4k
7 votes

Knapsack Greedy Approximation: Worst Case

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been ...
user avatar
7 votes

Please explain a greedy algorithm in a naive manner

In simple words, an algorithm is normally considered "greedy" if it builds solutions step by step without backtracking in each step it picks what's best in the current state. To learn more about it,...
user avatar
7 votes
Accepted

Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word. e.g. 3 SAT: (a,b,-c) && (-b,c) => pairs: (a,-a), (...
user avatar
7 votes
Accepted

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

You are on the right track. It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding ...
user avatar
  • 34.8k
6 votes
Accepted

Do all greedy algorithm produce just the first solution, no matter how bad it is?

Yes, this is the idea of greedy algorithms, also known as myopic algorithms. There is still a lot of freedom in deciding what the myopic choice is based on. Allan Borodin has developed a theory of ...
user avatar
6 votes
Accepted

Can sampling remove the limitations in greedy algorithm?

It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as myopic ...
user avatar
6 votes

Greedy and backtracking solutions to an arrangement problem with constraints

Overview of the problem If you takes teenagers as vertices of a graph, and have an edge whenever the two teenagers are compatible. This gives you an undirected graph, and what you need is a ...
user avatar
  • 19.1k
6 votes

greedy algorithm for Maximum directed cut

The starting point is the trivial random algorithm that chooses $S$ completely at random. Each directed edge is cut with probability $1/4$ (why?), and so in expectation, this random algorithm gives a $...
user avatar
6 votes
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 ...
user avatar
  • 4,537
6 votes

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 ...
user avatar
5 votes

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, "...
user avatar
  • 13.7k
5 votes

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 ...
user avatar
5 votes

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 ...
user avatar
5 votes

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 ...
user avatar
5 votes
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-...
user avatar
  • 25.5k
5 votes
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 ...
user avatar
  • 143k
5 votes
Accepted

Greedy algorithms: Minimum sum number pairing

Suppose that numbers are $x_1, \ldots x_{2n}$, and let us rename them as $a_1, \ldots a_n, b_1, \ldots, b_n$, where $a_i \geq b_j$ for any $i, j$, $a_1 \geq a_2 \geq \ldots \geq a_n$, and $b_1 \leq ...
user avatar
  • 195
5 votes
Accepted

Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

The greedy algorithm is optimal. The simple observation is that any optimal $k$ digits to remove must contain the rightmost digit in the initial non-decreasing digits of A, or one of its equivalents....
user avatar
  • 34.8k
4 votes
Accepted

Greedy proof: Correctness versus optimality

You can use whatever proof method you want. Proofs aren't even limited to existing patterns such as "greedy stay ahead" and "swapping". Indeed, in some cases, such as the greedy algorithm for ...
user avatar
4 votes

Coin Change Problem(Greedy Algorithm)

For the set of coins (2,3,11). $\frac{3}{2}<\frac{11}{3}$ so by your assumption we can be greedy here. Consider the value of 23. The greedy strategy would involve first taking 2 11 cent coins to ...
user avatar
  • 1,602
4 votes

Correctness of the greedy algorithm

The example provided by Valentin Lorentz can be slightly modified to break your solution for one order of traversal: 1 0 0 1 0 0 0 0 0 0 0 0 You can build a ...
user avatar
  • 416
4 votes
Accepted

Information about ε-greedy algorithms

ε-greedy is just a way to promote exploration in Reinforcement Learning. I would not classify SARSA or Q-Learning as ε-greedy algorithms. The latter are very common reinforcement learning algorithms ...
user avatar
  • 315
4 votes
Accepted

Dynamic Programming vs Greedy - coin change problem

A dynamic approach would say that "x$ can be made out of change using, as the first coin, v1 or v2 or v3 ... or vn" and then build a table so that the second coin would be v1 or v2 or v3 ... or vn + ...
user avatar
  • 56
4 votes
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 ...
user avatar
4 votes
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 ...
user avatar
  • 34.8k
4 votes
Accepted

Merging balls interview problem

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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible