# Questions tagged [greedy-algorithms]

An algorithm which at every point makes the locally optimal choice.

29 questions
Filter by
Sorted by
Tagged with
4k views

### Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
925 views

### Max-Cut algorithm that shouldn't work, unclear why

OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic: Given an undirected graph $G=(V,E)$, ...
2k views

### Does every greedy algorithm have matroid structure?

It is well established that for every matroid $M$ and any weight function $w$, there exits an algorithm $\mbox{GreedyBasis}(M,w)$ which returns a maximum weight basis of $M$. So, is the reverse ...
2k views

### What greedy algorithm satisfies greedy choice property but does not have optimal substructure?

Based on the textbook Introduction to Algorithms, the correctness of a greedy algorithm requires a problem to have two properties: greedy choice property optimal substructure It is easy to come up ...
467 views

### Why is the Greedy Conjecture so difficult?

I recently learned about the Greedy conjecture for the Shortest Superstring Problem. In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ ...
357 views

### How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
852 views

### Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?

Greedy is a non-formal term, but it could be (not sure, that's why I'm asking) that for certain problems, greediness can be mathematically formulated and thus be proven that no optimal greedy ...
407 views

543 views

### Huffman Tree Depth, Is there any theory?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ...
The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...