The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability

We consider the algorithm by Ferson et al. (Reliab Comput 11(3):207--233, 2005) designed for solving the NP-hard problem of computing the maximal sample variance over interval data, motivated by robust statistics. The formulation can be written as anonconvex quadratic optimization problem with a specific structure.First, we design a new version of the algorithm improving its original time bound \(O(n^2 \cdot 2^\omega)\) $O(n^2·2^{\omega })$ to \(O(n \log n+n\cdot 2^\omega)\) $O(nlogn+n·2^{\omega })$ ,where n is the size of input data and \(\omega\) $\omega$ is the clique number in a certain intersection graph. Then, we treat input data as random variablesand introduce a natural probabilistic data generating model. We get \(2^\omega = O(n^{1/\log\log n})\) $2^{\omega }=O(n^{1/loglogn})$ on average. This results in average computing time \(O(n^{1+\epsilon})\) $O(n^{1+ϵ})$ for \(\epsilon > 0\) $ϵ>0$ arbitrarily small, which may be considered as surprisingly good average-time complexity for solving an NP-hard problem.We also prove the following tail bound on the distribution of computation time: hard instances, forcingthe algorithm to compute in time \(2^{\Omega(n)}\) $2^{\mathrm{\Omega }(n)}$ , occur rarely,with probability tending to zero at rate \(e^{-n\log\log n}\) $e^{-nloglogn}$ .The main result admits a smoothed-complexity interpretation: the average computing time can be bounded by \(n^{1+\frac{O(1/\sigma)}{\log\log n}}\) $n^{1+\frac{O(1/\sigma )}{loglogn}}$ , where \(\sigma\) $\sigma$ measures the dispersion of the distribution of data perturbation.