<p>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&gt;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 <a href="https://en.wikipedia.org/wiki/Longest_path_problem">https://en.wikipedia.org/wiki/Longest_path_problem</a>.</p>

CC BY-SA 3.0
2016-03-24T06:27:21.717Z
2016-03-24T06:27:21.717Z
David Eppstein
<p>I have a function f(x, y) which takes two integers and returns a scalar.</p>

<p>My task is to find the set of (x, y) pairs, 0&lt;x&lt;W, 0&lt;y&lt;H where f(x, y)&gt;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 &lt; x1+y1).</p>

<p>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.</p>

<p>Can anybody tell me what class of problems this problem belongs to?</p>

<p>I attach a screenshot of a solution to one configuration (darker means higher f(x, y)). 
<a href="https://i.sstatic.net/XZ2EK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XZ2EK.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2016-03-23T16:34:44.297Z
Your problem belongs to the class P, the class of problems that are solvable in polynomial time.
Gamow
<graph-algorithms>
How do I describe this (graph-)problem for a research paper?
bgp2000
# How do I describe this (graph-)problem for a research paper?

(Asked by: username_0 on 2016-03-23)

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, 00, 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](https://i.sstatic.net/XZ2EK.png)](https://i.sstatic.net/XZ2EK.png)

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: Your problem belongs to the class P, the class of problems that are solvable in polynomial time.  

---

## 1 answers

### Answer by username_2 on 2016-03-24. Score: 5 | Accepted answer

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>.


---

