Interval data and sample variance: Expected computational complexity of upper bound
Ondřej Sokol, Miroslav Rada, Michal Černý · AIP conference proceedings · 2017
Computation of the tight upper bound on the sample variance of an interval-valued dataset is known to be NP-hard. However, using Ferson’s algorithm, the computation of the maximal possible variance over interval-valued dataset can be realized in polynomial time in the maximal number of narrowed intervals intersecting at one point; narrowed means that the intervals are shrinked proportionally to the size of the dataset. Simulation experiments allowed to conjecturing that the maximal number of narrowed intervals intersecting at one point is at most of logarithmic size for a reasonable choice of the data-generating process. Here, we assume uniform distribution of centers and constant radii. Under this setting, we sketch an approach how to prove the polynomiality of computation of upper bound of sample variance over random data.