approximation-algorithms

Approximation Algorithms

Overview

Approximation answers are certificate audits, not heuristic endorsements. First decide whether the problem is minimization or maximization, identify a polynomial-time lower or upper bound on the optimum, then prove the returned feasible solution is within the promised factor under the chapter's exact preconditions.

Core principle: never claim an approximation ratio from a good-looking local rule. Name the optimum bound, prove feasibility, prove the ratio against that bound, and reject the claim if any precondition, encoding assumption, or shortcut inequality is missing.

Shared CLRS Conventions

• Follow the parent clrs skill for mathematical formatting: every cost ratio, probability, recurrence, inequality, asymptotic bound, threshold, and approximation factor belongs in a display LaTeX block.
• Keep tables verbal. Put ratio definitions, LP constraints, probabilities, trimming guarantees, and running times in display blocks near the table instead of inside table cells.
• Use np-completeness for exact decision hardness and reductions; use this skill when the task asks for near-optimal algorithms, approximation ratios, inapproximability gaps, schemes, or approximation proof certificates.
• Use linear-programming for general LP modeling; use this skill when an LP relaxation is being rounded to certify an approximation algorithm.
• Do not announce that you are using this skill. Deliver the polished algorithm, proof, counterexample, or review directly.

When to Use

Use this skill for:

• proving or refuting an approximation ratio for a polynomial-time algorithm;
• distinguishing exact, pseudo-polynomial, PTAS, and FPTAS claims;
• checking metric TSP, general TSP, vertex cover, set cover, MAX-3-CNF, weighted vertex cover, or subset-sum approximation arguments;
• turning a greedy, randomized, LP-rounding, or trimming proof into a certificate-style answer;
• reviewing chapter problem patterns such as bin packing, weighted set cover, maximal matching, list scheduling, maximum spanning tree, maximum clique, or knapsack approximations.