¿Por qué las relaciones de aproximación diferencial no están bien estudiadas en comparación con las estándar a pesar de sus beneficios declarados?

16

Existe una teoría de aproximación estándar donde la relación de aproximación es supAOPT (para problemas conobjetivosMIN),A- el valor devuelto por algún algoritmoAyOPT- un valor óptimo. Y otra teoría, la deaproximación diferencialdonde la relación de aproximación esinfΩAΩOPT ,- el peor valor de una solución factible para la instancia dada. Losautoresde esta teoría afirman que tiene algunas ventajas definidas sobre la clásica. Por ejemplo:Ω

  • proporciona la misma relación de aproximación para problemas tales como cobertura de vértice mínima y conjunto independiente máximo que se sabe que son solo diferentes realizaciones del mismo problema;
  • da la misma proporción para las versiones máxima y mínima del mismo problema. Al mismo tiempo, sabemos en teoría estándar que MIN TSP y MAX TSP tienen relaciones muy diferentes.
  • Mide la distancia no solo al óptimo sino también al pesario . Entonces, en el caso de Vertex Cover, la teoría de aproximación estándar dice que es el mejor límite superior. Pero essentialy es la relación máxima entre el pesario y el óptimo. Por lo tanto, se garantiza que dicho algoritmo generará la solución con el peor valor.2 2Ω22

Mi argumento a favor es: en el análisis asintótico no tomamos en consideración las constantes y los términos de bajo orden (aquí recordé la cita de Avi Widgerson: "Tenemos éxito porque usamos el nivel correcto de abstracción") y este es el nivel de abstracción para comparar el uso de recursos del algoritmo. Pero cuando estudiamos la aproximación, por alguna razón, introducimos la diferencia en aquellos lugares donde podemos evitarla.

Mi pregunta es

¿Por qué la teoría de aproximación diferencial tan poco estudiada? ¿O los argumentos involucrados no son lo suficientemente fuertes?

Oleksandr Bondarenko
fuente
2
Nunca antes había visto esta noción y creo que es al menos interesante. Muy curioso por las respuestas! (aunque la verdadera razón puede ser tan trivial como "Doh, nunca pensé en eso" o "Las pruebas se están volviendo más difíciles" o "No puedo compararlo con otros resultados cuando comienzo")
Raphael

Respuestas:

3

Hay dos interpretaciones de la afirmación "el algoritmo encuentra una aproximación α del problema P "AαP :

  1. El problema es fácil de resolver bastante bien, ya que tenemos un algoritmo que encuentra una buena aproximación.P
  2. El algoritmo es bueno , ya que encuentra una buena aproximación.A

Creo que la definición clásica del factor de aproximación enfatiza la primera interpretación. Clasificamos los problemas de acuerdo con su facilidad de resolución.

La relación de aproximación diferencial parece poner un poco más de peso en la segunda interpretación: no queremos "recompensar" algoritmos triviales (por ejemplo, algoritmos que solo generan un conjunto vacío o el conjunto de todos los nodos).

Por supuesto, ambos son puntos de vista válidos, pero son puntos de vista diferentes .


También podemos estudiar la pregunta desde una perspectiva un poco más práctica. Desafortunadamente, las cubiertas de vértices como tales no tienen tantos usos directos, pero por razones de argumento, consideremos estas dos aplicaciones (algo artificiales):

  • Cubierta del vértice: los nodos son computadoras y los bordes son enlaces de comunicación; queremos monitorear todos los enlaces de comunicación y, por lo tanto, al menos un punto final de cada borde debe ejecutar un proceso especial.

  • Conjunto independiente: los nodos son trabajadores y los conflictos del modelo de bordes entre sus actividades; queremos encontrar un conjunto de actividades sin conflictos que se puedan realizar simultáneamente.

Ahora ambos problemas tienen una solución trivial: el conjunto de todos los nodos es una cubierta de vértice, y el conjunto vacío es un conjunto independiente.

La diferencia clave es que con el problema de la cubierta de vértices, la solución trivial hace el trabajo . Claro, estamos usando más recursos de los necesarios, pero al menos tenemos una solución que podemos usar en la práctica. Sin embargo, con el problema del conjunto independiente, la solución trivial es completamente inútil . No estamos progresando en absoluto. Nadie esta haciendo nada. La tarea nunca se completa.

Del mismo modo, podemos comparar soluciones casi triviales: vértice cubierta , que consiste en los extremos de un acoplamiento máximo, y el conjunto independiente I que es el complemento de C . Nuevamente, C ciertamente hace el trabajo en nuestra aplicación, y esta vez no estamos desperdiciando recursos en más del factor dos. Sin embargo, yo podría volver a ser un conjunto vacío, que es completamente inútil.CICCI

Por lo tanto, la definición estándar de la garantía de aproximación nos dice directamente si la solución es útil o no. Una aproximación de 2 de la cubierta del vértice hace el trabajo. Un conjunto independiente sin ninguna garantía de aproximación podría ser completamente inútil.

En cierto sentido, la relación de aproximación diferencial intenta medir "cuán no trivial" es la solución, pero ¿importa en alguna de estas aplicaciones? (¿Importa en alguna aplicación?)

Jukka Suomela
fuente
No entiendo tu punto en la segunda parte. Cualquier elección aproximada de vértices es una cubierta de vértice factible, no necesitamos saber que el algoritmo es una aproximación de 2 para eso. Por otro lado, incluso una aproximación de 2 para un conjunto independiente podría muy bien dar una solución inviable. Por lo tanto, parece que el peligro de inviabilidad está ligado al problema, no a límites de aproximación (no) conocidos.
Raphael
@Raphael: una aproximación 2 del conjunto independiente máximo es, por definición, un conjunto independiente (y bastante grande; ciertamente no es un conjunto vacío).
Jukka Suomela
No importa, lee demasiado rápido. Pero aún así, creo que su punto debería expresarse así: un algoritmo sin garantía de aproximación hace el trabajo en caso de VC, pero no en IS. (Está comparando manzanas y peras allí, ¿no es así?) Pero entonces, ¿cómo se relaciona este estudio con la elección de la garantía? Cualquiera de los dos haría para optar por soluciones viables.
Raphael
O(Δ)
1
+1 porque los ejemplos son divertidos. No creo que haya una diferencia bien definida entre "el problema es fácil" y "hay un buen algoritmo", pero lo entiendo a un nivel vago.
Tsuyoshi Ito
3

No estoy familiarizado con la noción de aproximación diferencial, y no tengo ninguna teoría de por qué no está bien estudiada. Sin embargo, me gustaría señalar que no siempre es deseable describir el rendimiento de un algoritmo de aproximación con una sola medida. En este sentido, me resulta difícil aceptar que alguna medida sea mejor que otra.

Por ejemplo, como usted indicó, la cobertura mínima de vértice admite un algoritmo de aproximación 2 de tiempo polinómico, mientras que es difícil de NP aproximar el conjunto independiente máximo a cualquier relación constante. Aunque entiendo que esto puede ser sorprendente a primera vista, tiene un significado legítimo: (1) la cobertura mínima de vértice se puede aproximar bien cuando es pequeña pero (2) no se puede aproximar bien cuando es grande. Cuando afirmamos que es NP-difícil aproximar la cobertura mínima del vértice (y el conjunto independiente máximo) con cualquier relación de aproximación diferencial constante positiva, estamos ignorando efectivamente la propiedad (1). Probablemente sea lo suficientemente bueno para algunos propósitos ignorar la propiedad (1), pero ciertamente no siempre es así.

Tenga en cuenta que no siempre usamos la relación de aproximación para describir el rendimiento de los algoritmos de aproximación. Por ejemplo, para establecer un resultado de inaproximabilidad basado en el teorema de PCP en toda su generalidad, necesitamos la formulación basada en problemas de brecha. Vea mi respuesta a otra pregunta para más detalles. En este caso, ni usar la relación de aproximación estándar ni usar la relación de aproximación diferencial nos permite establecer el resultado en la generalidad completa.

Tsuyoshi Ito
fuente
Un problema con la relación de aproximación estándar es que no nos da información sobre la calidad real de la aproximación en el sentido de que no muestra cuán distante es esta aproximación de la peor solución. Tenga en cuenta que este no es el caso con la relación estándar para problemas con el objetivo máximo, ya que si la aproximación coincide con la peor solución, tenemos la aproximación . En el caso de Vertex Cover tenemos una relación 2, aunque la aproximación coincide con la peor solución cuando O P T n /02OPTn/2
@Oleksandr: “En el caso de Vertex Cover, aunque la aproximación coincide con la peor solución cuando OPT⩾n / 2 tenemos la relación 2”. Si lo considera como una desventaja o no, es un punto de vista. Se puede argumentar que si cada solución tiene el valor objetivo dentro de un factor de 2, entonces no importa mucho qué solución produce un algoritmo. La relación de aproximación estándar modela la situación de esta manera.
Tsuyoshi Ito
Si este factor de 2 o cualquier otro factor pequeño es la peor solución, entonces dicho resultado es de poca utilidad.
Oleksandr Bondarenko
1
@Oleksandr: Como dije, ese es un punto de vista.
Tsuyoshi Ito
3

Como señala Tsuyoshi, el problema podría ser para qué tipo de argumento desea utilizar el límite obtenido. A continuación, intentaré desarrollar dos motivaciones diferentes.

α=AOPT

Relaciones diferenciales de la forma α=ΩAΩOPTα100%

Por lo tanto, dependiendo de qué tipo de declaración respalde el límite derivado, debe elegir la alternativa adecuada.

[Ω,OPT]

Rafael
fuente