## A Fun Optimization Problem

February 9, 2013 Leave a comment

I spent the last several hours trying to come up with an efficient algorithm to the following problem:

**Problem:** Suppose that we have a sequence of pairs of non-negative numbers such that and . Devise an efficient algorithm to find the pairs that maximize

**Commentary:** I don’t have a fully satisfactory solution to this yet, although I do think I can find an algorithm that runs in time and finds pairs that do at least as well as the best set of pairs. It’s possible I need to assume something like instead of just (and similarly for the ), although I’m happy to make that assumption.

While attempting to solve this problem, I’ve managed to utilize a pretty large subset of my bag of tricks for optimization problems, so I think working on it is pretty worthwhile intellectually. It also happens to be important to my research, so if anyone comes up with a good algorithm I’d be interested to know.