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

DOI10.1007/s00037-024-00254-3MaRDI QIDQ6599765

Ondřej Sokol, Michal Černý, Miroslav Rada

Publication date: 6 September 2024

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

tail probabilitynonconvex quadratic programmingaverage complexity

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Quadratic programming (90C20)

Cites Work

• A note on variability of interval data
• Computing statistics under interval and fuzzy uncertainty. Applications to computer science and engineering
• Computational complexity and feasibility of data processing and interval computations
• The complexity of computation and approximation of the \(t\)-ratio over one-dimensional interval data
• Partial identification of probability distributions.
• Average-case complexity without the black swans
• Exact bounds on finite populations of interval data
• Discrete Dynamic Programming and Capital Allocation
• Smoothed analysis of algorithms
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Random Geometric Graphs
• Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
• Random knapsack in expected polynomial time

This page was built for publication: The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability