A Lower Bound for Randomized Read-k-Times Branching Programs

Martin Sauerhoff

Published in: Electron. Colloquium Comput. Complex. (1997)

Keyphrases

lower bound
upper bound
randomized algorithms
randomized algorithm
branch and bound algorithm
lower bounding
optimal solution
lower and upper bounds
objective function
branch and bound
np hard
orders of magnitude
linear programming relaxation
sufficiently accurate
worst case
data structure