I have a function f(x, y) which takes two integers and returns a scalar.

My task is to find the set of (x, y) pairs, 0<x<W, 0<y<H where f(x, y)>0, which maximize the sum f(x_i, y_i) with the constraint that no two pairs shall overlap. Two pairs (x1, y1) and (x2, y2) overlap if (x2 >= x1 and x2 < x1+y1).

I have implemented a practical solution which processes in O(WxH) time with O(W) memory. I'm pretty sure this is optimal. It seems to me that it is a kind of a graph flow algorithm, but I don't know how to formally describe it without pseudo code.

Can anybody tell me what class of problems this problem belongs to?

I attach a screenshot of a solution to one configuration (darker means higher f(x, y)). enter image description here

  • $\begingroup$ Your problem belongs to the class P, the class of problems that are solvable in polynomial time. $\endgroup$ – Gamow Mar 23 '16 at 16:34

Replace any negative value with zero. Then, think of the numbers in the range $1\dots W$ as vertices in a graph, and think of a pair $(x,y)$ as corresponding to an edge from vertex $x$ to vertex $x+y$ (or to $W$ if $x+y>W$), with weight $f(x,y)$. This graph is a DAG, and what you are looking for are the nonzero edges on a longest path from $1$ to $W$ in this DAG. DAG longest path problems can be solved in time linear in the size of the DAG (here, $O(WH)$); see https://en.wikipedia.org/wiki/Longest_path_problem.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.