¿Cuáles son algunos ejemplos de problemas de optimización NP-hard que requieren métodos aproximados (como Monte Carlo)? He investigado mucho pero no encuentro un problema adecuado para implementar aparte del Problema del Viajante de Comercio
Respuesta
¿Demasiados anuncios?
En realidad, la lista es casi interminable, solo de memoria ahora (agregaré enlaces más tarde):
-
Selección de modelos dispersos: encontrar; $$\underset{\pmb\beta\in\mathbb{R}^p|\pmb{X},\pmb{y}}{\arg\min} ||\pmb y-\pmb\beta\pmb{X}||+|\pmb\beta|_0$$ [3].
-
Detección de valores atípicos: encontrar el subconjunto de $n/2$ de $n$ observaciones que minimicen una función de pérdida limitada, como (para el LTS): $$\underset{\pmb\beta\in\mathbb{R}^p|\pmb{X},\pmb{y}}{\arg\min} \sum_{i=1}^{n/2}(\pmb y-\pmb\beta\pmb{X})_{(i)}^2$$ [2].
-
Encontrar: $$\underset{H|\pmb{X}}{\arg\min}(\pmb x_i-\pmb x_j)'\pmb{C}^{-1}(\pmb x_i-\pmb x_j)|i\neq j \in H$$ donde $\pmb C=\underset{i\neq j\in H}{\text{ave}}(\pmb x_i-\pmb x_j)(\pmb x_i-\pmb x_j)'$ y $H$ es un subconjunto de $n/2$ observaciones de $n$ [1].
-
Encontrar: $$\underset{\pmb\mu\in\mathbb{R}^p}{\arg\min}\;\text{abs } \text{det}(V(\pmb{Z},\pmb\mu))$$ donde $\pmb{Z}=\{\pmb{x}_i\},i\in 1,\ldots,n:|\pmb Z|=p+1$ y $V(\pmb{Z},\pmb\mu)=\left(\begin{matrix} \pmb{1}_{p} & 1 \\ \pmb{Z} & \pmb{\mu} \end{matrix}\right)$ y $\pmb{1}_{p}$ es un vector de unos de tamaño $p$[0].
-
[0] Affine Invariant Multivariate Sign and Rank Tests y Estimaciones Correspondientes: Una revisión de Hannu Oja. Scandinavian Journal of Statistics, Vol. 26, No. 3 (Sep., 1999), pp. 319-343.
-
[1] Estimadores generalizados de S Christophe Croux, Peter J. Rousseeuw y Ola Hossjer. Journal of the American Statistical Association, Vol. 89, No. 428 (Dic., 1994), pp. 1271-1281
-
[2]IEEE Trans Image Process. 2013 May;22(5):1836-47. doi: 10.1109/TIP.2013.2237914. Publicación en línea 2013 Ene 9. Ajuste aproximado de la suma mínima recortada y aplicaciones en análisis de imágenes. Shen, Shen C, van den Hengel, Tang Z.
-
[3] Una nota sobre la complejidad de la minimización de Lp. Dongdong Ge, Xiaoye Jiang, Yinyu Ye.
Pero se podrían citar un montón de otros...
