Approximation guarantees, heuristics and FPT

For minimisation, α-approximation guarantees ALG≤α·OPT on admissible instances. “99% correct” is not a general definition. Maximisation uses a different ratio direction. Heuristics may perform well without a proven bound. A PTAS is polynomial in n for each fixed ε; an FPTAS is also polynomial in 1/ε.

Taking both endpoints of a maximal matching gives a 2-approximation for vertex cover: an optimum must cover each disjoint matching edge. Metric TSP relies on triangle inequality for shortcutting; its guarantees do not transfer to unrestricted TSP. Greedy set cover has a logarithmic bound, not universal optimality.

FPT separates a small parameter k from n: f(k)·n^c differs from n^k. Branching on an uncovered edge gives a vertex-cover search with O(2^k·poly(n)) time. Kernelisation reduces to an equivalent smaller instance. State the guarantee and its assumptions together.

def cover_approx(edges):
    remaining=list(edges); chosen=set()
    while remaining:
        u,v=remaining[0]; chosen.update((u,v))
        remaining=[(a,b) for a,b in remaining if a not in (u,v) and b not in (u,v)]
    return chosen
edges=[(0,1),(1,2),(2,3)]
c=cover_approx(edges)
assert all(u in c or v in c for u,v in edges)