Legyen P egy minimalizációs probléma: Adott egy I véges halmaz, c költségfüggvénnyel. Válasszuk ki a legkisebb költségû elemét I-nek. Legyen opt(I,c) ennek a költsége.
Jó lenne egy ezt megoldó algoritmust találni, de sokszor ilyet nem tudunk megadni. Ekkor beérjük kevesebbel is: Olyan A algoritmussal, amely I egy elemét adja outputként. Legyen A(I,c) az A outputjának költsége. Egy ilyen algoritmus persze csak akkor hasznos, ha valamilyen garanciánk van, hogy az output nem túl rossz eleme I-nek.
Definíció: A egy a-approximációs algoritmus, ha alkalmas b számra minden (I,c) esetén A(I,c)< a.opt(I,c)+b.
Megjegyzés: Természetesen a>=1. Természetesen a fogalom maximalizálási problémákra is kiterjeszthetõ.
Az alábbiakban egy speciális probléma megoldásán keresztül világítjuk meg a fenti fogalmat.
Az utazó ügynök probléma inputja egy G gráf, élein egy költségfüggvénnyel. Amit keresünk egy minimális költségû Hamilton-kör G-ben. (Az éleken értelmezett költségfüggvény természetes módon kiterjeszthetõ élhalmazokra, sétákra. Ha G-ben nincs Hamilton-kör, akkor az output legyen végtelen.)
Megjegyzés: Feltehetõ, hogy G egy teljes gráf. A továbbiakban ezzel a feltevéssel élünk is.
Az utazó ügynök problémára nem ismert hatékony algoritmus. A továbbiakban egy egyszerûbb változatot vizsgálunk.
Definíció: (G,c) elegettesz a háromszögegyenlõtlenségnek, ha G minden e=xy, f=yz és g=xz élére c(e)+c(f)>=c(g). Az utazó ügynök probléma háromszögegyenlõtlenségnek elegettevõ inputokra is nehéz. Az alábbiakban erre a kérdésre adunk két approximációs algoritmust.
1. lépés: Keressünk minimális kötségú feszítõ fát G-ben:
2. lépés: T éleinek megduplázásával keletkezõ T' gráfban keressünk zárt Euler-vonalat: V-t. V a gráf összes csúcsát bejárja.
3. lépés: V-t egyszerûsítsük úgy, hogy az összes csúcs maglátosatását még véghez vigye. Egy egyszerûsítõ lépés: egy többszöor;sen meglátogatott csúcs egyik meglátogatását kihagyjuk. Ez az egyszerûsítõ lépést addig ismételgetjülk, amíg Hamilton-körhöz nem jutunk. Ez lesz az algoritmus outputja.
Tétel: A fenti algoritmus 2-approximációs algoritmus.
1. lépés: Keressünk minimális kötségú feszítõ fát G-ben:
2. lépés: Legyen Q a T fa páratlan fokú csúcsainak halmaza. Keressünk Q-t párosító minimális költségû párosítást G-ben. Legyen ez M.
3. lépés: T éleihez adjuk hozzá éldiszjunkt módon M éleit. Az így keletkezõ T' gráfban keressünk zárt Euler-vonalat: V-t. V a gráf összes csúcsát bejárja.
4. lépés: V-t egyszerûsítsük úgy, hogy az összes csúcs maglátosatását még véghez vigye. Egy egyszerûsítõ lépés: egy többszöor;sen meglátogatott csúcs egyik meglátogatását kihagyjuk. Ez az egyszerûsítõ lépést addig ismételgetjülk, amíg Hamilton-körhöz nem jutunk. Ez lesz az algoritmus outputja.
Tétel: A fenti algoritmus 3/2-approximációs algoritmus.