4 ms·
I'm not sure this is right. Take a star with many (>3) leaves Replace every leaf by a star The algorithm fails by picking up leaves
by downshun 6y ago
I'm not sure this is right.
Take a star with many (>3) leaves
Replace every leaf by a star
The algorithm fails by picking up leaves
- saagarjha 6y agoIf you pick up a leaf, you also pick up the star one level up and thus the entire subtree is now covered (so you don’t look at it again). What is the failure, specifically?
- downshun 6y agoTrue. Hmm.
- 0xfaded 6y agoAssuming your star is a single center vertex which is a vertex to all edges (like spokes in a wheel), then the optimal cover for all edges is 1, the central vertex. If you follow the algorithm, you will select two vertices and produce a covering, which is within a factor of two of the optimal. I remember proving this algorithm in class (a while ago). What I found interesting from Wikipedia is that this is the best known approximation, there is a proven lower bound of 1.363.
- lalaland1125 6y agoYour intuition was right in that explanation provided in this proof is incorrect.. https://www.cl.cam.ac.uk/teaching/1415/AdvAlgo/lec8_ann.pdf https://www.cl.cam.ac.uk/teaching/1415/AdvAlgo/lec8_ann.pdf has a more complete explanation. The algorithm works (and gets a 2x bound), but only because of how it processes the edges sequentially and makes sure to only process edges that aren't already covered.