perfect utility maximization is impossible in all but the most trivial of situations.

I disagree with the paradigm behind this sentence of the paper. Just like we don't complain that perfect utility maximization is impossible in poker because we don't know all the cards, we shouldn't complain that perfect utility maximization is impossible in the travelling salesman problem because we can't compute all the routes. Instead we change paradigms - in poker, we change to maximizing expected utility, and in computationally limited problems we change to using computation time well and maximizing logical-probability expected utility.