Algorithms to Live By: The Computer Science of Human Decisions

by Brian Christian

For one thing, the spanning tree, with its free backtracking, will never be any longer than the real solution, which has to follow all the rules. Therefore, we can use the relaxed problem—the fantasy—as a lower bound on the reality.