Yaklaşım garantileri, heuristics ve FPT

Minimization için α-approximation, her uygun girdide ALG≤α·OPT garantisidir. “%99 doğru” genel bir tanım değildir. Maximization oranının yönü ayrıca belirtilir. Heuristic iyi çalışabilir ama kanıtlı oran sunmayabilir. PTAS her sabit ε için polinom n süresiyle (1+ε) oranı; FPTAS ayrıca 1/ε bakımından polinom süre ister.

Vertex cover için maximal matching uçlarını seçmek 2-approximation verir: her matching kenarı en az bir optimum vertex ister; seçilen uçlar bunun iki katıdır. Metric TSP'de triangle inequality shortcut'ı mümkün kılar; genel TSP'ye metric garantisini taşımak yanlıştır. Greedy set cover logarithmic bound sunar, her greedy optimal değildir.

Parameterized complexity, n ile küçük k'yı ayırır. FPT süre f(k)·n^c biçimindedir; n^k genel olarak FPT değildir. Vertex cover için açık kenarın bir ucunu seçerek dallanma O(2^k·poly(n)) verir. Kernelization eşdeğer küçük örnek oluşturur. Approximation, randomization ve parameterization farklı araçlardır; raporda garanti ve varsayımı birlikte göster.

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)