Skip to main content
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 ...
Alex Golovnev's user avatar
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, ...
Yixin Cao's user avatar
  • 2,559
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 ...
lacker's user avatar
  • 256
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 ...
reservoir's user avatar
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. ...
Neal Young's user avatar
  • 10.8k

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