Proporcionar un ejemplo estricto en el análisis de algoritmos de aproximación

8

Digamos que encontré un algoritmo de aproximación de 2 para un problema determinado y quiero mostrar que el análisis es estricto.

¿Necesito ahora encontrar un ejemplo de tamaño genérico o es suficiente para mostrar que tengo un ejemplo de tamaño para el cual el algoritmo produce ?n102OPT

stev
fuente

Respuestas:

6

Eso depende de su definición de relación de aproximación. Normalmente, la relación de aproximación se define como la peor relación entre la solución óptima y la producida por su algoritmo. Si este es el caso, todo lo que necesita para demostrar que la relación es ajustada es un mal ejemplo.

A veces, sin embargo, demuestra algo como . Esto significa que su relación de aproximación es realmente . Para demostrar que esto es estricto, necesitará un ejemplo para infinitos tamaños (pero no necesariamente para un tamaño genérico ; quizás todos sus ejemplos tengan un tamaño par).ALG2OPT+12+o(1)

Yuval Filmus
fuente
3

Si su algoritmo logra una aproximación de 1.5 en todas las instancias de excepto un conjunto finito , en el cual su algoritmo logra una aproximación de 2, entonces podría "mejorar" su algoritmo "cableando" las soluciones óptimas para las instancias en en su algoritmo . En resumen, para fines teóricos, un algoritmo que tiene éxito en todas las instancias, excepto en un conjunto finito, es tan bueno como un algoritmo que siempre tiene éxito. Por lo tanto, un ejemplo ajustado teóricamente significativo es en realidad una familia infinita de ejemplos ajustados. Como dice Yuval, cualquier familia infinita de ejemplos servirá, no necesita un ejemplo para cada tamaño de instancia.SS

Dicho esto, la mayoría de los problemas le permiten "ampliar" un pequeño ejemplo a uno más grande.

Sasho Nikolov
fuente
Pero si hay demasiadas instancias malas en las que desea que el algoritmo se conecte, ¿no se encuentra con el problema de que su algoritmo ya no se ejecuta en polytime, ya que tiene que verificar qué caso de cableado se aplica?
user695652
@ user695652 "finito" significa que . puede elegir qué caso aplicar en el tiempo . por supuesto, eso podría ser una ENORME constante, pero esa es la naturaleza del análisis asintótico. S|S|=O(1)O(1)
Sasho Nikolov