Title: Time-accuracy trade-offs for hard maximization problems