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 QIDQ6599765FDOQ6599765

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

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

Cites Work

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6599765)