CMP.5:5 - Archetypal Grounding

CMP.5:5.1 - Recover indivisible choices from a fractional solution

In weighted vertex cover, a graph represents pairs that must be covered. Selecting a vertex covers its incident edges and incurs nonnegative cost w(v). The original problem minimizes sum w(v)*z(v) with z(v) equal to 0 or 1 and z(u)+z(v)≥1 on every edge.

Allow 0≤z(v)≤1 instead. Every integral cover remains feasible, so the fractional minimum is a lower bound. Obtain a fractional solution x and select every vertex with x(v)≥1/2. Each edge has an endpoint at least one half, so the selected vertices cover every edge. This derives feasibility of the rounding rule.

For each selected vertex, w(v)≤2*w(v)*x(v). Summing over selected vertices, and using nonnegative weights for the remaining terms, gives C≤2*sum w(v)*x(v). If x attains the fractional minimum, the recovered cover costs at most twice the original optimum. A merely feasible fractional point gives the displayed cost comparison but does not alone establish that approximation factor.

Consider a triangle with unit vertex costs. Setting every fractional value to one half gives value 1.5. Adding the three edge inequalities gives 2*sum x(v)≥3, proving that 1.5 is the fractional minimum. Threshold rounding selects all three vertices with cost 3. Removing one vertex leaves a valid cover with cost 2, improving the initial candidate. Original costs are integers, so the lower bound 1.5 also implies an original cost of at least 2. The recovered cover is therefore optimal for this instance.

Changed constraint: add “select at most one vertex.” The fractional vector with all values one half violates this new constraint, and the recovered two-vertex cover is also inadmissible. If the cardinality constraint is deliberately dropped in the relaxation, 1.5 can remain a lower bound for feasible original solutions, but it provides no feasible cover. On a triangle one selected vertex always leaves the opposite edge uncovered, so the new original problem is infeasible. The previous recovery rule cannot be reused as a solution.

CMP.5:5.2 - Use a relaxed answer as a search bound

A robot moves on the finite grid with coordinates 0≤x≤2, 0≤y≤1. It can move one horizontal or vertical step at unit cost. The task is to go from (0,0) to (2,0); cell (1,0) is blocked.

Ignore blocked cells in the relaxed problem. The distance is abs(dx)+abs(dy), here 2. Every permitted original route is also a relaxed route with the same cost, so 2 is a lower bound. The straight relaxed route is unusable. An admissible detour through (0,1),(1,1),(2,1) costs 4, giving an initial comparison 2≤optimum≤4.

CMP.4 can use the relaxed remaining distance at each partial route, together with the distance already traveled. Alternatively, the blocked direct row implies that a valid route must include an upward and a downward move in addition to two horizontal moves, proving a lower bound of 4. That stronger argument closes this small case. The relaxed result was useful without being mistaken for an executable original route.

Changed operations: allow diagonal moves at unit cost. The earlier Manhattan distance can overestimate: reaching (1,1) from (0,0) can cost 1 rather than 2. Relax the new movement problem instead. With unrestricted unit-cost horizontal, vertical and diagonal moves, max(abs(dx),abs(dy)) is the distance and supplies the corresponding lower bound. The algorithmic thinking consists in rebuilding the comparison after the operations change.