Exponential Lower Bounds for the Pigeonhole Principle

Paul Beame Russell Impagliazzo Jan Krajícek Toniann Pitassi Pavel Pudlák Alan R. Woods

Published in: STOC (1992)

Keyphrases

lower bound
upper bound
average case complexity
branch and bound algorithm
objective function
branch and bound
optimal solution
worst case
lower and upper bounds
np hard
optimal cost
quadratic assignment problem
lower bounding
randomly generated problems
exponential size