La importancia de la brecha de integralidad

44

Siempre tuve problemas para comprender la importancia de la brecha de integralidad (IG) y sus límites. IG es la proporción de (la calidad de) una respuesta entera óptima a (la calidad de) una solución real óptima de la relajación del problema. Consideremos la cubierta de vértice (VC) como un ejemplo. Se puede afirmar que VC encuentra una solución entera óptima del siguiente conjunto de ecuaciones lineales:

Tenemos cero / uno variables de valor xv s para cada vértice vV(G) de la gráfica G . Las ecuaciones son: 0xv1 para vV(G) y 1xv+xu para cada borde uvE(G) . Estamos buscando valores que minimicen vV(G)xv .

La relajación de este problema permite valores reales entre 0 y 1 por lo que el espacio de soluciones es mayor y una solución real óptima puede ser más pequeña que una solución entera óptima que queremos encontrar. Por lo tanto, necesitamos realizar un proceso de "redondeo" en la respuesta real óptima obtenida de la programación lineal para encontrar una solución entera. La solución entera óptima estará entre la solución real óptima y el resultado del proceso de redondeo. IG es la relación de una solución entera óptima a una solución real óptima y no dice nada sobre el proceso de redondeo. El proceso de redondeo puede (en teoría) ignorar completamente la solución real y calcular la solución entera óptima directamente.

¿Por qué las personas están interesadas en probar los límites de IG?

Kaveh
fuente
8
Dos no respuestas: (1) informática empírica. Con bastante frecuencia (¡ciertamente no siempre!) Parece ser el caso de la brecha de integralidad ≈ la dureza de la aproximación, al menos bajo algunos supuestos. Por lo tanto, si no tiene idea de lo difícil que es aproximar el problema X, probar límites estrechos en la brecha de integralidad podría darle una suposición informada. Tienes al menos una conjetura que puedes intentar probar. (2) Si su algoritmo rompe la brecha de integralidad, entonces podría ser una señal de que su algoritmo está haciendo algo interesante (como explotar buenas propiedades combinatorias del problema específico).
Jukka Suomela
3
Charles, las brechas de integralidad son un área activa dentro de la teoría de la complejidad en estos días. A menudo, las personas prueban brechas para grandes familias de relajación (en lugar de una sola relajación). En este caso, puede pensar en tales resultados como probar límites inferiores contra un modelo computacional interesante. También hay conexiones profundas para probar la complejidad.
Moritz

Respuestas:

30

xx

Entonces, ¿por qué no inventar otra relajación LP o cambiar a otras técnicas y seguir adelante? La programación lineal y convexa ha demostrado ser central para los algoritmos de aproximación; Para muchos problemas, la brecha de integralidad de una formulación LP o SDP natural es igual a la relación de aproximación del mejor algoritmo, así como a la dureza de la relación de aproximación. Esto es solo una observación empírica, pero significa que probar una brecha de integralidad puede sugerir consecuencias mucho más fuertes de un algoritmo mejorado o límite inferior.

Puede haber razones más profundas y rigurosas para este fenómeno. Por ejemplo, suponiendo la conjetura de los juegos únicos, se sabe que la relación de aproximación y la relación de inaproximabilidad para los problemas de satisfacción de restricciones es igual a la brecha de integralidad de una relajación simple de SDP (ver Algoritmos óptimos y Resultados de inaproximabilidad para cada CSP? Por Prasad Raghavendra)

PNP

Ian
fuente
21

aca/ca1/c

II

Luca Trevisan
fuente
17

La brecha de integralidad es un indicador útil de qué tan bien se puede aproximar una IP. Sería mejor pensarlo de manera informal e intuitiva. Una gran brecha de integralidad implica que ciertos métodos no funcionarán. Ciertos métodos primarios / duales, por ejemplo, dependen de una pequeña brecha de integralidad. Para el LP Vertex Cover LP estándar estándar, el LP dual solicita una coincidencia máxima. En este caso, podemos hacer lo siguiente:

  • encuentre una solución fraccional óptima para el LP doble (una coincidencia fraccional máxima)y
  • multiplique la solución por un factor de 2 (doble todos los pesos de borde)y
  • convierta esto en una integral factible para el LP primario (cada borde da la mitad de su peso del vector a cada uno de sus puntos finales en el vector , entonces cada es reemplazado con ).x2yxximin(xi,1)

En este caso, esta estrategia simple funciona y terminamos con una solución integral factible para el LP primario cuyo peso no es más del doble del peso de una solución factible para el LP dual. Dado que el peso de una solución factible para el LP doble es un límite inferior para OPT, este es un algoritmo de aproximación de 2.

Ahora, ¿dónde entra la brecha de integralidad? El IG es 2 en este caso, pero eso solo no implica que el algoritmo funcionará. Más bien, sugiere que podría funcionar. Y si el IG fuera más de 2, garantizaría que la estrategia simple no siempre funcionaría. Como mínimo, tendríamos que multiplicar la solución dual por el IG. Entonces, la brecha de integralidad a veces nos dice lo que no funcionará. La brecha de integralidad también puede indicar qué tipo de factor de aproximación podemos esperar. Una pequeña brecha de integralidad sugiere que investigar estrategias de redondeo, etc., podría ser un enfoque que valga la pena.

Para un ejemplo más interesante, considere el problema de Hitting Set y la poderosa técnica de aproximación del problema usando -nets (Brönnimann y Goodrich, 1995) . Muchos problemas pueden formularse como instancias de Hitting Set, y una estrategia que ha tenido éxito para muchos problemas es hacer esto, luego simplemente encontrar un buen buscador de redes, es decir, un algoritmo para construir pequeñas redes , y poner todo en marcha El meta-algoritmo de B&G. Entonces la gente (incluido yo mismo) trata de encontrar buscadores de red para instancias restringidas de Hitting Set que, para cualquier , pueden construir una -net de tamaño , donde la funciónεεεεf(1/ε)fdebe ser lo más pequeño posible. Tener es un objetivo típico; esto daría una aproximación .f(1/ε)=O(1/ε)O(1)

Como resultado, la mejor función posible está limitada por la brecha de integralidad de cierto LP para Hitting Set (Even, Rawitz, Shahar, 2005) . Específicamente, las soluciones integrales y fraccionales óptimas satisfacen . Para instancias sin restricciones de Hitting Set, la brecha de integralidad es , pero al formular otro problema como Hitting Set, el IG puede ser menor. En este ejemplo, los autores muestran cómo encontrar -nets de tamañofOPTIf(OPTf)Θ(log(m))εO((1/ε)loglog(1/ε))para las instancias restringidas de Hitting Set que corresponden al problema de golpear cajas paralelas al eje. De esta manera, mejoran el factor de aproximación más conocido para ese problema. Es un problema abierto si esto se puede mejorar o no. Si, para estas instancias restringidas de Hitting Set, el IG para Hitting Set LP es , sería imposible diseñar un buscador de red que garantice -nets de tamaño , ya que hacerlo implicaría la existencia de un algoritmo que garantiza conjuntos de golpes integrales de tamaño , pero desdeΘ(loglogm)εo((1/ε)loglog(1/ε))o(OPTfloglogOPTf)OPTfmEsto implicaría una brecha de integralidad menor. Entonces, si la brecha de integralidad es grande, probar que podría evitar que las personas pierdan su tiempo buscando buenos buscadores de redes.

James King
fuente
13

Cuando se te ocurre un algoritmo de aproximación para algún problema de maximización de NP-hard, hay varios valores que te pueden interesar: hay OPT, el valor óptimo de tu problema, que es lo mismo que OPT (IP), el óptimo valor de cualquier formulación correcta de IP de su problema. También existe OPT (LP), el valor óptimo de la relajación lineal de su IP.

OPT(LP)OPT(IP)

Finalmente, está V, el valor de la solución que obtienes al redondear la solución LP. Le gustaría poder probar que para mostrar que su algoritmo es una aproximación , pero a menudo no es posible hacerlo directamente, ya que no tiene un Espera en el espacio de la solución. En cambio, lo que casi siempre se prueba es que . Por supuesto, esto implica , pero es más fuerte. En particular, si la brecha de integralidad de su formulación de IP es mayor que , la declaración anterior será falsa en general, ya que su procedimiento de redondeo termina con una solución integral.V>OPT(IP)ccVOPT(LP)cV>OPT(IP)cc

Entonces, el quid es este: el LP le brinda una solución que usted sabe que es "buena", y desea redondearla a algo que sea "casi tan bueno". Si la brecha de integralidad es grande, esto es imposible en general, ya que nunca habrá un procedimiento que garantice obtener una solución integral que sea "casi tan buena" como una solución LP, porque a veces, ¡estos no existen!

Aaron Roth
fuente
12

Tiene razón en que la brecha de integralidad de una relajación no tiene nada que ver con ningún algoritmo de redondeo. Estas son dos nociones diferentes. Una brecha de integralidad es una propiedad de una relajación particular. Es decir, ¿cuánto más grande es el valor de esa relajación en comparación con el valor integral óptimo?

¿Por qué nos importan las relajaciones lineales / convexas? Aproximar eficientemente un valor integral. Por lo tanto, típicamente hablamos de relajaciones solo en casos en los que el valor óptimo es difícil de calcular y estamos interesados ​​en aproximaciones eficientes. Las brechas de integralidad nos muestran las limitaciones inherentes de lo que se puede lograr con tales técnicas.

Entonces, ¿por qué nos preocupamos por los algoritmos de redondeo además de la relajación? Utilizamos algoritmos de redondeo para resolver el problema algorítmico de encontrar una solución casi óptima en lugar de solo aproximar el valor de una solución óptima. Además, a menudo se utilizan algoritmos de redondeo para unir la brecha de integralidad de una relajación en primer lugar.

Moritz
fuente
Exactamente, parece que las personas están interesadas en las formulaciones de IP y sus relajaciones debido a los algoritmos de aproximación para el problema original, pero no entiendo lo que aprendemos sobre los algoritmos de aproximación resultantes al probar un límite en IG.
Kaveh
11

Técnicamente, la brecha de integralidad es para una formulación de IP específica, no (como la formuló) la relación entre la mejor relajación lineal y la solución óptima (que parece cuantificar sobre TODAS las formulaciones de IP).

Una brecha de integralidad es importante porque muestra los límites de la formulación particular de LP que se está utilizando. Si sé que una relajación particular tiene una brecha de integralidad de , entonces también sé que si alguna vez espero probar un límite mejor que , necesitaré usar una formulación diferente.cc

Suresh Venkat
fuente
Hola suresh Gracias, sabía que IG es para una formulación de IP específica, lo siento si no lo dije correctamente. Lo que no entiendo es la relación de IG con algoritmos de aproximación y la respuesta final que obtenemos al final del proceso de redondeo. Me parece que IG es una propiedad geométrica de una relajación real específica del problema original y su relación con los algoritmos de aproximación no está clara para mí. Quiero saber más sobre las razones que hacen que los límites en IG sean interesantes, especialmente con respecto a los algoritmos de aproximación.
Kaveh
Hola Kaveh, traté de aclarar específicamente esos puntos en mi respuesta. Quizás ayude.
Moritz
3
Una respuesta particularmente fascinante a su pregunta es el ataque Swart en P vs NP al tratar de construir un programa lineal para TSP que tuviera soluciones enteras. Mihalis Yannakakis escribió este hermoso artículo que luego mostró que NO la relajación simétrica de TSP admitía una formulación de tamaño de poli con soluciones enteras ( dx.doi.org/10.1016/0022-0000(91)90024-Y ).
Suresh Venkat
6

Hubo un documento muy interesante "Sobre la ventaja de la codificación de red para mejorar el rendimiento de la red", que mostró que la brecha de integralidad de la "relajación de corte bidireccional" para el problema del árbol Steiner equivale exactamente a un tipo de "ventaja de codificación" en la comunicación de red. No conozco muchos otros documentos similares. Sin embargo, también se debe tener en cuenta que se conocen relajaciones de LP aparentemente mejores para el problema del árbol de Steiner (por ejemplo, vea el nuevo algoritmo de aproximación basado en LP hipergráfico de Byrka et al en STOC 2010, también me ofrezco descaradamente como voluntario de que coautoré algunos artículos recientes que estudian el hipergráfico LP).

daveagp
fuente
6

La mayoría de las respuestas ya han abordado la razón principal para preocuparse por la brecha de integralidad, a saber, que un algoritmo de aproximación basado únicamente en el uso del límite proporcionado por la relajación no puede demostrar una relación mejor que la brecha de integralidad. Permítanme dar otras dos razones meta por las cuales la brecha de integralidad es una guía útil. Para una gran clase de problemas de optimización combinatoria, la equivalencia de separación y optimización muestra que los algoritmos exactos están íntimamente relacionados con el casco convexo de las soluciones factibles para el problema. Así, la perspectiva geométrica y algorítmica están muy unidas entre sí. No se conoce una equivalencia formal similar para los algoritmos de aproximación, pero es una guía útil: los algoritmos van de la mano con relajaciones geométricas. La innovación algorítmica ocurre cuando las personas tienen un objetivo concreto para mejorar.

Chandra Chekuri
fuente