Por lo general, se piensa en soluciones aproximadas (con garantías) a problemas NP-hard. ¿Hay alguna investigación en curso para aproximar problemas que ya se sabe que están en P? Esta podría ser una buena idea por varias razones. Fuera de mi cabeza, un algoritmo de aproximación puede ejecutarse con una complejidad mucho menor (o incluso una constante mucho más pequeña), podría usar menos espacio o podría ser mucho mejor paralelizable.
Además, los esquemas que proporcionan compensaciones de tiempo / precisión (FPTAS y PTAS) pueden ser muy atractivos para problemas en P con límites inferiores que son inaceptables en entradas grandes.
Tres preguntas: ¿hay algo que me falta que haga que esto sea obviamente una mala idea? ¿Hay investigaciones en curso para desarrollar una teoría de estos algoritmos? Si no, al menos, ¿alguien está familiarizado con ejemplos individuales de tales algoritmos?
fuente
Respuestas:
Como señala Jukka, la geometría computacional es una rica fuente de problemas que se pueden resolver en tiempo polinómico, pero deseamos obtener aproximaciones rápidas. El clásico resultado "ideal" es un "LTAS" (esquema de aproximación de tiempo lineal) cuyo tiempo de ejecución sería de la forma ; por lo general, estos se obtienen mediante la extracción de una constante (poli ( 1 / ϵ )) dimensionó el núcleo a partir de los datos y ejecutó un algoritmo costoso en ese núcleo, con la garantía de que una solución exacta en el núcleo es una solución aproximada en toda la entrada.O ( n + poli ( 1 / ϵ ) ) 1 / ϵ
Hay una serie de trucos, reducciones y principios, y el nuevo libro de Sariel Har-Peled está lleno de estos. No creo que haya una teoría rica en complejidad como tal.
fuente
Lista no exhaustiva de trabajos recientes que encuentran soluciones aproximadas para problemas enPAGS
1) Hay una gran cantidad de trabajo sobre soluciones aproximadas para ecuaciones lineales (simétricas diagonalmente dominantes) en un tiempo casi linealO (n⋅polylog(n))
(lista de documentos) http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html
(En general, la mayoría de los solucionadores iterativos de ecuaciones lineales comparten el principio de aproximación la solución verdadera. Lo mismo ocurre con los métodos iterativos que resuelven problemas más generales (por ejemplo, algunos programas convexos / lineales)).ϵ
2) Soluciones aproximadas para min / max cortes / flujos http://people.csail.mit.edu/madry/docs/maxflow.pdfs - t
3) Encontrar una aproximación dispersa de la transformada de Fourier de una señal en tiempo sublineal http://arxiv.org/pdf/1201.2501v1.pdf
4) Encontrar el componente principal aproximado de una matriz http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf
fuente
No conozco una teoría general desarrollada sobre algoritmos de aproximación para problemas en P. Sin embargo, conozco un problema particular que se llama oráculos de distancia aproximada:
Hay una compensación tripartita entre espacio, tiempo de consulta y aproximación en el problema del oráculo de distancia. Uno puede responder trivialmente cada consulta exactamente (aproximación = ) en tiempo O ( 1 ) almacenando la matriz de distancia de todos los pares; o en tiempo O ( m + n log n ) ejecutando un algoritmo de ruta más corta. Para gráficos masivos, estas dos soluciones pueden requerir un espacio prohibitivamente grande (para almacenar la matriz) o tiempo de consulta (para ejecutar un algoritmo de ruta más corta). Por lo tanto, permitimos la aproximación.1 O ( 1 ) O ( m + n logn )
Para gráficos dispersos, se puede mostrar una compensación de espacio-aproximación-tiempo más general .
fuente
A menudo buscamos soluciones aproximadas a problemas simples como encontrar la ruta más corta en un gráfico, encontrar el número de elementos únicos en un conjunto. La restricción aquí es que la entrada es grande y queremos resolver el problema aproximadamente usando un solo paso sobre los datos. Existen varios algoritmos de "transmisión" diseñados para lograr soluciones aproximadas en tiempo lineal / casi lineal.
fuente
Se conocen algoritmos de aproximación rápida para una coincidencia máxima. Al menos uno que me viene a la mente de inmediato es http://arxiv.org/pdf/1112.0790v1.pdf .
fuente
fuente
Creo que toda el área de transmisión de datos y algoritmos sub-lineales es un esfuerzo en esta dirección. En la transmisión de datos, la atención se centra en resolver los problemas en el espacio o (n) e idealmente O (polylog (n)), mientras que en los algoritmos sub-lineales intenta obtener algoritmos con el tiempo de ejecución o (n). En ambos casos, a menudo es necesario comprometerse con tener un algoritmo de aproximación aleatorio.
Puede comenzar con el material en esta página y esto .
fuente
fuente
Dimitris menciona transformaciones de Fourier aproximadas. hay un amplio uso de esto en la compresión de imágenes, por ejemplo, en el algoritmo JPEG. [1] aunque no he visto un artículo que enfatice esto, parece que, en cierto sentido, una compresión con pérdida [2] (con límites derivables) también se puede tomar como un algoritmo de aproximación de tiempo P. Los aspectos de aproximación están altamente desarrollados y ajustados / especializados en el sentido de que están optimizados para que no puedan ser percibidos por la visión humana, es decir, la percepción humana de los artefactos de codificación (definida aproximadamente como la diferencia entre la aproximación y la compresión sin pérdidas) se minimiza.
Esto está relacionado con las teorías sobre cómo el ojo humano percibe o en sí mismo "aproxima" la codificación del color a través de algún proceso de tipo algorítmico. en otras palabras, el esquema / algoritmo de aproximación teórico está diseñado intencionalmente para que coincida con el esquema / algoritmo de aproximación física / biológica (codificado por procesamiento de información biológica, es decir, neuronas en el sistema visual humano).
entonces, la compresión está estrechamente acoplada con la aproximación. en JPEG, la transformada de Fourier es aproximada por la DCT, transformada discreta del coseno [3]. principios similares se emplean en múltiples cuadros para el estándar de compresión de video MPEG. [4]
[1] compresión jpeg, wikipedia
[2] compresión con pérdida, wikipedia
[3] DCT, transformada discreta del coseno, wikipedia
[4] MPEG, wikipedia
fuente
Puede ser que esto no responda exactamente a su pregunta, porque actualmente solo puedo recordar algunas heurísticas, pero estoy seguro de que hay algunas aproximaciones, porque las vi antes.
fuente
http://www.sciencedirect.com/science/article/pii/S0020019002003939
es un enlace al artículo "Un algoritmo de aproximación simple para el problema de correspondencia ponderada" por Doratha Drake y Stefan Hougardy que cubre el problema de correspondencia ponderada.
fuente