I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.
They mention that the 2-approximation ratio is a lower bound. How is a maximal matching a lower bound? Does it mean that it is the lowest approximation value we can get compared to $log n$ of the greedy algorithm that is polynomial?
The images below show the optimal vertex cover = 8 but and a maximal matching of 12.
I decided to find another matching which I later discovered is called a maximum matching from Wikipedia. Since a maximum matching is also a maximal matching, I assume that this the worst that we can get, a maximum matching of 16 vertices.
How can one improve on the edges picked then? My 16 vertices versus the book’s 12?