Normalmente escucho sobre relajaciones en un contexto de optimización. En ese caso, estás aflojando algunas de las restricciones para que el espacio de la solución sea mayor y el problema que termines sea más fácil de resolver que el problema original.
Por ejemplo, si está buscando minimizar la forma cuadrática [matemática] x ^ TWx [/ matemática] con las restricciones [matemática] x \ in \ {- 1, 1 \} ^ n [/ matemática], tiene un Problema NP-duro. La relajación estándar es reemplazar las restricciones con [matemáticas] x \ en [-1, 1] ^ n [/ matemáticas], lo que le da un problema fácil de resolver. Además, puede utilizar la solución que obtenga para encontrar una buena solución al problema original.
Lo que he descrito es similar a la relajación de programación lineal, que es un método estándar para derivar algoritmos de aproximación. La programación semidefinida es otro buen objetivo para la relajación de un problema difícil.
- Criptografía: ¿Cómo explicaría el encadenamiento de hash para evitar la técnica de colisiones de hash?
- ¿Cuáles son los mejores momentos 'aha' que tiene cuando resuelve problemas de matemáticas / programación?
- ¿Qué es un algoritmo para convertir de una lista de adyacencia a una matriz de incidencia?
- Cómo formular un programa entero donde todos estén representados en un horario
- Informática teórica: ¿cómo empiezo a resolver el problema P = NP?
