Computing variance for interval data is NP-hard

ABSTRACT

When we have only interval ranges [xi, xi] of sample values x1,…, xn, what is the interval [V, V] of possible values for the variance V of these values? We prove that the problem of computing the upper bound V is NP-hard. We provide a feasible (quadratic time) algorithm for computing the lower bound V on the variance of interval data. We also provide a feasible algorithm that computes V under reasonable easily verifiable conditions.

REFERENCES

• 1: V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl, Computational complexity and feasibility of data processing and interval computations, Kluwer, Dordrecht, 1997.
• 2: R. Osegueda, V. Kreinovich, L. Potluri, and R. Aló, "Non-Destructive Testing of Aerospace Structures: Granularity and Data Mining Approach", Proceedings of FUZZ-IEEE'2002, Honolulu, Hawaii, May 12-17, 2002 (to appear).
• 3: Stephen A. Vavasis, Nonlinear optimization: complexity issues, Oxford University Press, Inc., New York, NY, 1991
• 4: G. William Walster, Philosophy and practicalities of interval arithmetic, Reliability in computing: the role of interval methods in scientific computing, Academic Press Professional, Inc., San Diego, CA, 1988