On Lower Bounds for Computing the i-th Largest Element

Vaughan R. Pratt Foong Frances Yao

Published in: SWAT (1973)

Keyphrases

lower bound
upper bound
objective function
branch and bound
upper and lower bounds
worst case
branch and bound algorithm
vc dimension
lower and upper bounds
machine learning
computational complexity
randomly generated problems
database
max sat
optimal solution
decision trees
databases