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.