15

Actually, the complete and general description of a problem that can be solved by a greedy algorithm is a matroid embedding, which generalizes both the concept of a matroid and that of a greedoid. The answer is no—a problem solvable by a greedy algorithm need not have a matroid structure, but it will have the structure of a matroid embedding (which is, alas, ...


14

One of the standard estimators in robust statistics is a type of trimmed mean where you choose a majority subset of a set of input numbers in such a way as to minimize the maximum difference between any two selected numbers, and then take the mean of the selected subset. There's an easy greedy-choice first step: choose the median as part of your subset. But ...


13

My earlier claim of $\frac{2}{c+6}$ did not take into account the cut of size $n^2/4$ already present in the graph. The following construction appears to result (emperically - I have created a question at math.stackexchange.com for a rigorous proof) in a $O\left(\frac{1}{\log c}\right)$ fraction. The algorithm performs badly on unions of several ...


12

After a while of thinking and asking around, here's a counter-example, courtesy of Ami Paz: Let $n$ be even and $G$ be a graph which is the union of $K_n$ with a matching of $n+2$ vertices (that is, a matching with $n/2+1$ edges). How does the algorithm run on this graph? It just takes vertices from the clique part in arbitrary order. After having taken $k$...


11

Greedy algorithm is not a formally defined concept. There are various models trying to capture this intuitive notion but there is no consensus on what is a greedy algorithm. Unless you specify a formal definition of what you mean by a greedy algorithm the question cannot be answered as yes or no. There is a generalization of matroids called greedoid which ...


8

Let me first try to summarize what is known about the Greedy Conjecture. Blum, Jiang, Li, Tromp, Yannakakis prove that the Greedy Algorithm gives a 4-approximation, and Kaplan and Shafrir show that it gives a 3.5-approximation for the Shortest Common Superstring problem. A version of the greedy algorithm is known to give a 3-approximation (Blum, Jiang, Li, ...


6

I don't know of a way to compute the length of the code exactly without constructing a Huffman code. And there may be more than one optimal Huffman code for a given set of weighted items, with different lengths. But there has been some related theory on lengths of Huffman codes: Length-limited Huffman coding is a variant of Huffman coding where you are not ...


5

Unfortunately, the algorithm can be arbitrarily bad. In the following example, each vertex $u_i$ has $d$ disjoint neighbors, of which only four are drawn. The optimal solution is $\{u_1, \ldots, u_p, w_1, \ldots, w_d\}$, while the greedy algorithm returns its complement. The ratio is $\frac{d p}{p + d} \approx d$ with $p\to 0$.


4

The approximation guarantee will be significantly worse. Assume you want to cover the set $U=\{1,\ldots,2n\}$. For every $i=1,\ldots,n$ define a set with n+1 elements by $S_i=\{i,n+1,\ldots,2n\}$. Assume we want to cover U with the sets $C=\{S_1,\ldots,S_n,U\}$, where $c(U)=2, c(S_i)=1$. We would now start with $C$ ans see that the effectivity of the sets $...


3

Here's a reduction from 3SAT. For each of your 3SAT variables $x_0$, imagine there is one event $x_0$ and two rooms called "Room $x_0$ is true" and "Room $x_0$ is false". The event $x_0$ has to be in one of those two rooms. Whichever statement is true, that's the room we don't use. And it is going to take all day. So the only rooms generally available for ...


3

The main difference, in my view, is that DP solves subproblems optimally, then makes the optimal current decision given those sub-solutions. Greedy makes the "optimal" current decision given a local or immediate measure of what's best. Greedy doesn't reason about the subsequent choices to be made, so its measure of what's best is shortsighted and might be ...


2

Dynamic programming is not a greedy algorithm. It just embodies notions of recursive optimality (Bellman's quote in your question). A DP solution to an optimization problem gives an optimal solution whereas a greedy solution might not.


2

Consider following problems: COIN-CHAINING EURO: Given infinite amount of 1,2,5,10 euro notes, pay X euro using as few notes as possible. This can be solved by using greedy algorithm, which takes largest note possible. But there is no matroid structure in this problem. HOLE COVERAGE: There are holes in positions x_1, x_2, ..., x_n. You have patch of length ...


2

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows. Let $c=(\sqrt{17}-1)/2 \approx 1.56$. There are three objects of size $c$, $1$, and $1$. There are two bins of size $2$ and $c$. Initially $a=1$. Some heuristics will place the largest object into the big bin, necessitating $a$ increasing from 1 to at ...


1

This seems similar to bin-packing problem. I set $a=1$ and try to solve the bin-packing problem of putting objects of size $O_1$ to $O_n$. If I cannot find the solution then I increase $a$ with value $\delta >0$ and try again. If it doesn't work I increase $a$ by $2\delta$ and so on.


1

Maybe this would also interest you (adapted from Methods to translate global constraints to local constraints) Since greedy methods (more correctly local methods) employ only local information to achieve global optimisation, if ways are found which are able to transform global conditions to conditons able to be used employing only local information, this ...


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