A provable two-approximation

What this concept is

For minimization, an α-approximation returns a feasible solution of cost at most α times OPT on every input in the stated domain. It is not an empirical average or a guarantee about running time alone.

Why it matters here

When exact optimization is expensive, a bound gives an inspectable compromise. The approximation theorem must match the implemented problem, especially weights and constraints.

Concrete example

Scan unweighted graph edges. Whenever both endpoints are still unmatched, add the edge to M and both endpoints to C. The matching is maximal: after the scan no edge can be added while keeping endpoints disjoint. C covers every edge, since an uncovered edge would have had both endpoints unmatched when scanned and would have been selected. Every cover needs at least |M| vertices, while |C|=2|M|. Hence |C|≤2OPT.

Common confusion / misconception

Maximal is not maximum. Any maximal matching suffices for this proof. Returning only one endpoint of each matched edge need not cover the other edges. A matching lower bound need not equal OPT.

How to use it

Keep the matching as a certificate and verify it separately. Scanning an already normalized edge list takes O(n+m) work including initialization in a unit-cost model. The lab sorts/deduplicates edges for deterministic behavior, so preprocessing adds O(m log m), and storing vertices/edges uses O(n+m). Include these costs rather than reporting only the inner loop.

Check yourself

For a star, what can this algorithm return and what is OPT? Why can the ratio be exactly 2?

Mini drill or application

Give weights 100 and 1 to the endpoints of a single edge. Selecting both costs 101 while the weighted optimum costs 1. Explain why the unweighted factor-two proof cannot be reused for weighted cost.

Read this only if stuck

Use Erickson’s Algorithms and lecture notes for reductions and hardness, and the selective reading guide for the matching approximation. Full-book reading is not required.