New answers tagged

0

If your talking about programming, most languages default to include and and not b unless explicitly corrected. If your talking about a math or computer science problem, the problem must state explicitly if it's included or not. If it is not mentioned, it's basically a 50/50, though I'm pretty sure it's generally accepted that if it is not mentioned. you ...


-2

Find any solution in O(N) time using the greedy algorithm (keep moving the leaves, select parent of a leaf if the leaf is not selected or covered.) Initialize a counter vector to ones for the selected nodes. Check the selected nodes in vertex cover one by one and determine if you release that node and select any of its un-selected neighbors without violating ...


2

I don't have a reference for you, just a minor remark that is too large for a comment. We assume $w$ is chosen as follows. Choose r.v. $x\in[0,1]^n$ uniformly at random (i.e., each $x_i$ is i.i.d. uniformly in $[0,1]$), then set $w_i = x_i/X$, where $X=\sum_j x_j$. Then with high probability, almost all sets $S$ will have $\sum_{i\in S} w_i \sim 1/2$: ...


Top 50 recent answers are included