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:
Vanlige tilnærmingsstrategier inkluderer greedy-tilnærminger som ofte gir kjente garantier (for eksempel Set Cover og Vertex Cover),
Tilnærmingsalgoritmer brukes bredt i praksis når presise løsninger er for kostbare, for eksempel innen logistikk, planlegging