NP-Hard optimisation problems that require approximate methods What are some examples of NP-hard optimisation problem that requires approximate methods (such as Monte Carlo? I have done a lot of research but I can't find a suitable problem to implement apart from the Travelling Salesman Problem
 A: Actually, the list is nearly endless, just off the top of my head now ( I will add links later):


*

*Sparse model selection: finding;
$$\underset{\pmb\beta\in\mathbb{R}^p|\pmb{X},\pmb{y}}{\arg\min} ||\pmb y-\pmb\beta\pmb{X}||+|\pmb\beta|_0$$ [3].

*Outlier detection: finding the subset of $n/2$ out of $n$ observations that minimize a bounded loss function, such as (for the 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].

*Finding: 
$$\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$$ where $\pmb C=\underset{i\neq j\in H}{\text{ave}}(\pmb x_i-\pmb x_j)(\pmb x_i-\pmb x_j)'$ and $H$ is a subset of $n/2$ observation out of $n$ [1].

*Finding: 
$$\underset{\pmb\mu\in\mathbb{R}^p}{\arg\min}\;\text{abs } \text{det}(V(\pmb{Z},\pmb\mu))$$
where $\pmb{Z}=\{\pmb{x}_i\},i\in 1,\ldots,n:|\pmb Z|=p+1$ and 
$V(\pmb{Z},\pmb\mu)=\left(\begin{matrix}
  \pmb{1}_{p}  & 1 \\
  \pmb{Z} &  \pmb{\mu}
 \end{matrix}\right)$ and $\pmb{1}_{p}$ is a $p$ vector of ones[0].

*[0] Affine Invariant Multivariate Sign and Rank Tests and
Corresponding Estimates: A Review Hannu Oja. Scandinavian Journal of
Statistics, Vol. 26, No. 3 (Sep., 1999), pp. 319-343.

*[1] Generalized S-Estimators
Christophe Croux, Peter J. Rousseeuw and Ola Hossjer.
Journal of the American Statistical Association, Vol. 89, No. 428 (Dec., 1994), pp. 1271-1281

*[2]IEEE Trans Image Process. 2013 May;22(5):1836-47. doi: 10.1109/TIP.2013.2237914. Epub 2013 Jan 9.
Approximate least trimmed sum of squares fitting and applications in image analysis. Shen, Shen C, van den Hengel, Tang Z.

*[3] A Note on the Complexity of Lp Minimization. Dongdong Ge, Xiaoye Jiang, Yinyu Ye.


But one could cite tons of others...
