tilnærmingsalgoritmer

Tilnærmingsalgoritmer er algoritmer som gir nær-optimal løsninger for optimaliseringsproblemer der nøyaktige løsninger kan være beregningsmessig uoverkommelige, spesielt når problemet er NP-hard og stor skala gjør eksakte metoder urealistiske. Målet er å levere løsninger av høy kvalitet innen rimelig tid, og å kunne dokumentere hvor nærme løsningen er til optimalnivået.

En vanlig måte å beskrive kvaliteten på er gjennom en tilnærmingsgrad α som gjelder for alle instanser: for minimisering A(I) ≤ α·OPT(I), og for maksimering A(I) ≥ OPT(I)/α. Mange problemer har en PTAS (polynomial-time approximation scheme) som gir for hvilket som helst ε > 0 en løsning innen (1+ε) av optimal i tid som er polynomial i instansen, mens FPTAS er en sterkere variant som også er polynomisk i 1/ε. Noen problemer har bare en konstant-faktor tilnærming og tilhører APX-klassen.

Vanlige tilnærmingsstrategier inkluderer greedy-tilnærminger som ofte gir kjente garantier (for eksempel Set Cover og Vertex Cover), lokale søk, og avrunding av lineære programmer eller andre relaxation-teknikker. Eksempler på kjente resultater er Set Cover med log n-tilnærming, Vertex Cover med faktor 2, og metric TSP med 1.5-tilnærming (Christofides’ algoritme). 0/1 Knapsack har også en FPTAS.

Tilnærmingsalgoritmer brukes bredt i praksis når presise løsninger er for kostbare, for eksempel innen logistikk, planlegging og ressursallokering. Forskning fokuserer på hva som er teoretisk mulig, og på å kombinere teknikker for ulike typer problemer for å oppnå bedre garantier og effektivitet.