Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract).
Martin SauerhoffPublished in: STACS (1998)
Keyphrases
- extended abstract
- lower bound
- upper bound
- randomized algorithms
- randomized algorithm
- objective function
- branch and bound algorithm
- branch and bound
- np hard
- optimal solution
- lower bounding
- quadratic assignment problem
- lower and upper bounds
- orders of magnitude
- max sat
- online algorithms
- linear programming
- worst case
- set of randomly generated instances