Computing best-possible bounds for the distribution of a sum of several variables is NP-hard.
Vladik KreinovichScott FersonPublished in: Int. J. Approx. Reason. (2006)
Keyphrases
- np hard
- lower bound
- random variables
- worst case
- linear functions
- upper bound
- approximation algorithms
- spatial distribution
- weighted sum
- binary variables
- scheduling problem
- optimal solution
- marginal probabilities
- approximation guarantees
- min sum
- boolean variables
- variable selection
- neural network
- np complete
- special case
- knapsack problem
- upper and lower bounds
- branch and bound algorithm
- closely related
- objective function
- causal models
- joint distribution
- greedy heuristic
- large deviations
- branch and bound
- expected error
- dependence structure