9
votes
Why is the Greedy Conjecture so difficult?
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 ...
- 2,247
6
votes
Huffman Tree Depth, Is there any theory?
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 ...
- 50.9k
5
votes
Accepted
Is this greedy algorithm for vertex cover studied before?
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, ...
- 2,560
4
votes
Accepted
What is the reverse of greedy algorithm for setcover?
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\}$.
...
- 56
3
votes
Accepted
Interval partitioning with restrictions: NP-complete or efficiently solvable?
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 ...
- 256
3
votes
Accepted
Dynamic Programming vs Greedy Algorithm
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 ...
- 7,595
2
votes
Maximum Vertex Cover
Thanks @Neal Young for a nice solution. I already accepted your answer. I just wanted to point out, for future readers, where exactly I ''failed''.
So, what I had already shown (using @Neil's ...
- 89
2
votes
Accepted
Maximum Vertex Cover
Recall that $L=\max_{S\subseteq V : |S|=k} \sum_{v\in S} d(v) / 2$, where $d(v)$ is the degree of vertex $v$, and that, as observed in the post,
any set of $k$ vertices covers at most $2L$ edges.
...
- 9,595
2
votes
Dynamic Programming vs Greedy Algorithm
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 ...
- 121
2
votes
Accepted
Packing $n$ objects into $m$ bins whose size is variable
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$.
...
- 18.9k
1
vote
Packing $n$ objects into $m$ bins whose size is variable
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 $...
- 199
1
vote
Optimal greedy algorithms for NP-hard problems
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 ...
- 571
Only top scored, non community-wiki answers of a minimum length are eligible