The following approximation algorithm for the Minimal Dominating Set Problem is said by a fellow student to be a 1.5-approximation:
- Start with empty set $S$
- As long as not all vertices are covered:
- Add a vertex that is not in $S$ with the most uncovered neighbors including itself.
- Mark it and all its neighbors as covered
- return $S$
I can't find a proof for the approximation ratio however and my own attempts to prove it have failed so far since I lack the right approach to proof something like this.