Algoritme d'aproximació

En ciències de la computació i investigació d'operacions, un algoritme d'aproximació és un algoritme usat per a trobar solucions aproximades a problemes d'optimisació. Estan a sovint associats en problemes NP-hard; com és poc provable que alguna volta es descobrixquen algoritmes eficients de temps polinòmic que resolguen exactament problemes NP-hard, s'opta per trobar solucions no-òptimes en temps polinomial. A diferència de les heurístiques, que usualment solament troben solucions raonablement bones en temps raonablement ràpits, lo que es busca ací és trobar solucions que està demostrat són de calitat i els temps de la qual d'eixecució estan acotats per cotes conegudes. Idealment, l'aproximació millora la seua calitat per a factors constants menuts (per eixemple, dins del 5% de la solució òptima). Els algoritmes d'aproximació estan sent cada volta més utilisats per a resoldre problemes a on els algoritmes exactes de temps polinomial són coneguts pero massa costosos pel tamany de l'entrada.

Un eixemple típic per a un algoritme d'aproximació és un per a resoldre el problema de la cobertura de vèrtiços de la teoria de grafos: trobar una aresta no coberta i afegir els seus dos punts finals a la cobertura de vèrtiç, i repetir fins que ya no queden arestes. És clar que la cobertura resultant serà a lo més dos voltes del llarc de la solució òptima. Est és un algoritme d'aproximació de factor constant en un factor de 2.

Els problemes NP-hard varien molt en la seua aproximació; alguns, tals com el problema de la mochila, poden ser aproximats per mig de qualsevol factor superior a 1 (tal família d'algoritmes d'aproximació es coneix com esquema d'aproximació de temps polinomial o PTAS). Uns atres, com el problema del clan, són impossibles d'aproximar dins de qualsevol constant, o inclús factor polinomiales, a menos que P = NP.

Els problemes NP-hard freqüentment poden expressar-se com programació sancera (PE) i ser resolts exactament en temps exponencial. Molts algoritmes d'aproximació sorgixen de la relaixació de la programació llineal (PL), pròpia de la programació sancera.

No tots els algoritmes d'aproximació són adequats per a totes les aplicacions pràctiques. A sovint utilisen resolvedores (solvers) de IP, LP i programació semidefinida, estructures de senyes complexes o tècniques d'algoritmes sofisticades que tendixen a dificultar els problemes d'implementació. Ademés, alguns algoritmes d'aproximació posseïxen temps d'eixecució poc pràctics, inclús a pesar de ser polinòmics, com per eixemple, de l'orde d'O(n²⁰⁰⁰). No obstant, a pesar d'açò últim, existixen problemes a on els alts temps d'eixecució i costs de memòria poden justificar-se, tals com els relacionats en la biologia computacional, ingenieria financera, la planificació del transport, i la gestió d'inventari. En estos escenaris, es deu competir contra les corresponents formulació de programació sancera directa.

Una atra llimitació de l'aproximació és que esta solament és aplicable als problemes d'optimisació, i no als problemes de decisió en estat "pur", tals com SAT (a pesar de que és possible representar versions d'optimisació per a tals problemes, com el respectiu Problema de satisfacibilidad màxim).

Garanties de comportament

Per a alguns algoritmes d'aproximació és possible demostrar en certea propietats sobre l'aproximació del resultat òptim. Per eixemple, en el cas d'un ρ-algoritme d'aproximació s'ha demostrat que l'aproximació a no serà major (o menor, depenent de la situació) que un factor ρ voltes la solució òptima s.

$\{\begin{array}{c}s\le a\le \rho s,\text{if }\rho >1;\\ \rho s\le a\le s,\text{if }\rho <1.\end{array}$

El factor ρ es diu garantia de comportament relatiu (relative performance guarantee). Un algoritme d'aproximació té una garantia de comportament absolut o error acotat ε, si s'ha demostrat que

$(s-ϵ)\le a\le (s+ϵ).$

Análogamente, el radi de comportament aboluto (absolute performance ràtio) ${\mathrm{P}}_A$ d'un algoritme d'aproximació $A$, a on $I$ és una instància del problema, i $R_A(I)$ és la garantia de comportament de $A$ en $I$ (és dir, $\rho$ per a l'instància $I$ del problema) és:

${\mathrm{P}}_A=\inf \{r\ge 1|R_A(I)\le r,\mathrm{\forall }I\}$

Açò significa que ${\mathrm{P}}_A$ és la major cota en el radi d'aproximació, $r$, que un troba en totes les possibles instàncies del problema. De la mateixa manera, el radi de comportament asintòtic (asymptotic performance ràtio) $R_A^{\mathrm{\infty }}$ és:

$R_A^{\mathrm{\infty }}=\inf \{r\ge 1|\mathrm{\exists }n\in {\mathbb{Z}}^{+},R_A(I)\le r,\mathrm{\forall }I,I\ge n\}$

És dir, que és el mateix radi de comportament absolut, en una cota inferior $n$ en el tamany de les instàncies del problema. S'utilisen estos dos tipos de ràdio perque degut a que existixen algoritmes a on la diferència entre ells és significativa.

l'anàlisis de dominació (Domination analysis) proveïx un camí alternatiu per a analisar la calitat d'un algoritme d'aproximació, en térmens del ranc de la solució computada en la seqüència ordenada de totes les possibles solucions.

Referències

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, i Clifford Stein. Introduction to Algorithms, Segona Edició. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítul 35: Approximation Algorithms, pp.1022–1056.
• Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Capítul 9: Various Notions of Approximations: Good, Better, Best, and More.