Análisis de dominancia

El análisis de dominancia de un algoritmo de aproximación es una forma de estimar su rendimiento, introducida por Glover y Punnen en 1997. A diferencia del análisis clásico de la razón de aproximación , que compara la calidad numérica de una solución calculada con la de una solución óptima, el análisis de dominancia implica examinar la posición de la solución calculada en el orden de todas las soluciones posibles. En este tipo de análisis, se dice que un algoritmo tiene un número de dominancia o número de dominancia K , si existe un subconjunto de K soluciones diferentes al problema entre las cuales la salida del algoritmo es la mejor. El análisis de dominancia también puede expresarse mediante una razón de dominancia , que es la fracción del espacio de soluciones que no es mejor que la solución dada; este número siempre se encuentra dentro del intervalo [0,1], donde los números mayores indican mejores soluciones. El análisis de dominancia se aplica con mayor frecuencia a problemas para los que se conoce el número total de soluciones posibles y para los que la solución exacta es difícil.

Por ejemplo, en el problema del viajante , existen ( n -1)! posibles soluciones para una instancia con n ciudades. Si se demuestra que un algoritmo tiene un número de dominancia cercano a ( n -1)!, o equivalentemente, una razón de dominancia cercana a 1, entonces se puede considerar preferible a un algoritmo con un número de dominancia menor.

Si es posible encontrar de forma eficiente muestras aleatorias del espacio de soluciones de un problema, como ocurre en el problema del viajante, entonces resulta sencillo para un algoritmo aleatorio encontrar una solución que, con alta probabilidad, tenga una alta tasa de dominancia: basta con construir un conjunto de muestras y seleccionar la mejor solución entre ellas. (Véase, por ejemplo, Orlin y Sharma).

El número de dominancia que se describe aquí no debe confundirse con el número de dominancia de un grafo, que se refiere al número de vértices en el conjunto dominante más pequeño del grafo.

Recientemente, ha aparecido un número creciente de artículos que aplican el análisis de dominancia para evaluar el rendimiento de las heurísticas. Este tipo de análisis puede considerarse una alternativa al análisis clásico de la razón de aproximación. Sin embargo, ambas medidas también pueden verse como complementarias.

Esta sección contiene un análisis técnico de los resultados conocidos.

Inaproximabilidad. Sea ε > 0. A menos que P=NP , no existe un algoritmo polinomial para la cobertura de vértices. de tal manera que su número de dominación sea mayor que 3^((nn^ε)/3).

Inaproximabilidad. Sea ε > 0. A menos que P=NP, no existe un algoritmo polinomial para el problema de la mochila. de tal manera que su número de dominación sea mayor que 2^(nn^ε).

• Glover, F. y Punnen, AP (1997). "El problema del viajante: nuevos casos resolubles y vínculos con el desarrollo de algoritmos de aproximación". J. Oper. Res. Soc . 48 (5): 502– 510. doi : 10.1057/palgrave.jors.2600392 . S2CID 123498731 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
• Gutin, Gregory y Yeo, Anders (2004). "Introducción al análisis de dominación" (PDF) . Optimization Online.{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )
• Orlin, James B. y Sharma, Dushyant (2002). "El vecindario extendido: definición y caracterización" (PDF) .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )