<p>In a <a href="https://arxiv.org/abs/1701.02634" rel="nofollow noreferrer">recent paper</a>, we propose such a scheme. The scheme is illustated in a specific crowdsourcing application setting, but the idea is fairly simple. We just see the order constraint $\mu(u) \leq \mu(v)$ of each DAG edge $(u, v)$ as a linear inequality constraint, we consider the admissible convex polytope of assignments to these linear inequalities, and we choose the center of mass of this polytope as our interpolation result.</p>

<p>The paper explains the scheme in more detail, includes an algorithm, computational hardness results, an approximation scheme that derives from existing work, a tractable case when the DAG is a tree, and a discussion of alternate schemes.</p>

CC BY-SA 3.0
2017-01-21T00:01:26.840Z
2017-01-23T01:06:26.900Z
2017-01-23T01:06:26.900Z
Antoine Amarilli 'a3nm'
<p>Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a reasonable way is to perform linear interpolation: find the largest $j &lt; i$ such that $A[j]$ is known, find the smallest $k &gt; i$ such that $A[k]$ is known, and do a weighted average $A[j] := {k-i \over k-j}A[k] + {i-j \over k-j}A[j]$. In particular, this ensures that the following property (*) holds: </p>

<p>$$\text{if } A[j] \leq A[k] \text{ then } A[j] \leq A[i] \leq A[k]$$</p>

<p>Now, you can see an array as a totally ordered structure, and wonder about what would happen in the case of a partial order. Assume that I have a DAG $G = (V, E)$ of $n$ nodes where every node $v \in V$ has a numerical value $\mu(v)$ where some values are known and some are unknown (with the values of the roots and leaves assumed to be known). If I want to estimate some unknown $\mu(v)$, it seems that I should interpolate it out of the values of the closest ancestors and descendents of $v$ whose values are known. The question is: what should we do, exactly? Is there a generalization of linear interpolation in this setting?</p>

<p>[Here is a possible choice: for every couple $(u, w)$ of ancestors and descendents of $v$, perform linear interpolation along all the possible chains between $u$, $v$ and $w$ to get a value for $v$, and average all the values over all chains and ancestor-descendent pairs to get your final estimate. Is this the correct way to do things? Can this estimation be computed more efficiently than with this definition? (i.e., could we do it in linear time in the size of the neighborhood of $v$ under consideration, rather than in a quadratic way?). Do we still have some variant of property (*)? (note that, even if you assume monotonicity, i.e. for each ancestor-descendent couple $(u, w)$ you assume $\mu(u) \leq \mu(w)$, then the estimation $\mu(v)$ obtained by the previous process may still violate monotonicity, i.e. $\mu(v) &gt; \mu(u)$ for some ancestor $u$ of $v$)]</p>

CC BY-SA 3.0
2012-12-27T18:43:14.153Z
I'm guessing you assume the function $\mu$ is monotone along the partial order ? In particular, what would you do if for some interpolation paths $\mu$ decreases and for others it increases ?
Suresh Venkat
CC BY-SA 3.0
2012-12-27T18:50:37.237Z
Assuming that $\mu$ is monotone along the partial order (or Suresh's point is otherwise handled), it looks like basic memoization (to avoid redundant computation) would give a little win over the approach given in the question, at least on average (in the sense of performance on uniform DAGs), and especially so on low treewidth DAGs.
Daniel Apon
CC BY-SA 3.0
2012-12-27T19:24:48.463Z
I would reframe this problem as finding the best assignment of values to the nodes such that for each directed edge $(u,v)$ we have $A[u] < A[v]$.  **But what function are you trying to optimize?**  One natural choice that's consistent with standard linear interpolation is $\sum_{(u,v)} (A[v] - A[u])^2$, where the sum is over all edges of the dag, but is that what you actually want?
Jeffε
CC BY-SA 3.0
2012-12-27T20:01:28.677Z
Suresh Venkat: In the setting I have in mind, $\mu$ is indeed monotone, but even then things are weird (cf. the last sentence of my question). If it is not monotone, there might still be sensible things to do: for instance if there are two immediate ancestors with values -1 and 1, and two immediate descendents with values -1 and 1, then it seems reasonable to interpolate 0. JɛﬀE: I don't know the function I want to optimize, it's precisely my question: what is the most natural thing to optimize here to follow the spirit of a linear interpolation?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-12-27T20:43:52.493Z
I'm not convinced that the ordering of the array is relevant here. Notice that linear interpolation makes sense for points in an arbitrary dimensional space: find a simplicial decomposition and then do barycentric interpolation in the interior of a simplex. So considering a DAG (or a poset in general) is adding additional structure to the interpolation problem, which means you have an extra degree of freedom which you can **choose* to set. It's not entirely clear that there's a single "right" choice unless there is some other consideration deriving from the underlying problem.
Suresh Venkat
<ds.algorithms><reference-request><graph-algorithms><partial-order>
Generalizing linear interpolation to posets
Antoine Amarilli 'a3nm'
# Generalizing linear interpolation to posets

(Asked by: username_0 on 2012-12-27)

Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a reasonable way is to perform linear interpolation: find the largest $j < i$ such that $A[j]$ is known, find the smallest $k > i$ such that $A[k]$ is known, and do a weighted average $A[j] := {k-i \over k-j}A[k] + {i-j \over k-j}A[j]$. In particular, this ensures that the following property (\*) holds:

$$\text{if } A[j] \leq A[k] \text{ then } A[j] \leq A[i] \leq A[k]$$

Now, you can see an array as a totally ordered structure, and wonder about what would happen in the case of a partial order. Assume that I have a DAG $G = (V, E)$ of $n$ nodes where every node $v \in V$ has a numerical value $\mu(v)$ where some values are known and some are unknown (with the values of the roots and leaves assumed to be known). If I want to estimate some unknown $\mu(v)$, it seems that I should interpolate it out of the values of the closest ancestors and descendents of $v$ whose values are known. The question is: what should we do, exactly? Is there a generalization of linear interpolation in this setting?

[Here is a possible choice: for every couple $(u, w)$ of ancestors and descendents of $v$, perform linear interpolation along all the possible chains between $u$, $v$ and $w$ to get a value for $v$, and average all the values over all chains and ancestor-descendent pairs to get your final estimate. Is this the correct way to do things? Can this estimation be computed more efficiently than with this definition? (i.e., could we do it in linear time in the size of the neighborhood of $v$ under consideration, rather than in a quadratic way?). Do we still have some variant of property (\*)? (note that, even if you assume monotonicity, i.e. for each ancestor-descendent couple $(u, w)$ you assume $\mu(u) \leq \mu(w)$, then the estimation $\mu(v)$ obtained by the previous process may still violate monotonicity, i.e. $\mu(v) > \mu(u)$ for some ancestor $u$ of $v$)]

**Tags:** ds.algorithms, reference-request, graph-algorithms, partial-order
> **Comments:**
> **username_1**: I'm guessing you assume the function $\mu$ is monotone along the partial order ? In particular, what would you do if for some interpolation paths $\mu$ decreases and for others it increases ?  
> **username_2**: Assuming that $\mu$ is monotone along the partial order (or Suresh's point is otherwise handled), it looks like basic memoization (to avoid redundant computation) would give a little win over the approach given in the question, at least on average (in the sense of performance on uniform DAGs), and especially so on low treewidth DAGs.  
> **username_3**: I would reframe this problem as finding the best assignment of values to the nodes such that for each directed edge $(u,v)$ we have $A[u] < A[v]$.  **But what function are you trying to optimize?**  One natural choice that's consistent with standard linear interpolation is $\sum_{(u,v)} (A[v] - A[u])^2$, where the sum is over all edges of the dag, but is that what you actually want?  
> **username_0**: Suresh Venkat: In the setting I have in mind, $\mu$ is indeed monotone, but even then things are weird (cf. the last sentence of my question). If it is not monotone, there might still be sensible things to do: for instance if there are two immediate ancestors with values -1 and 1, and two immediate descendents with values -1 and 1, then it seems reasonable to interpolate 0. JɛﬀE: I don't know the function I want to optimize, it's precisely my question: what is the most natural thing to optimize here to follow the spirit of a linear interpolation?  
> **username_1**: I'm not convinced that the ordering of the array is relevant here. Notice that linear interpolation makes sense for points in an arbitrary dimensional space: find a simplicial decomposition and then do barycentric interpolation in the interior of a simplex. So considering a DAG (or a poset in general) is adding additional structure to the interpolation problem, which means you have an extra degree of freedom which you can **choose* to set. It's not entirely clear that there's a single "right" choice unless there is some other consideration deriving from the underlying problem.  

---

## 1 answers

### Answer by username_0 on 2017-01-21. Score: 2 | Accepted answer

In a [recent paper](https://arxiv.org/abs/1701.02634), we propose such a scheme. The scheme is illustated in a specific crowdsourcing application setting, but the idea is fairly simple. We just see the order constraint $\mu(u) \leq \mu(v)$ of each DAG edge $(u, v)$ as a linear inequality constraint, we consider the admissible convex polytope of assignments to these linear inequalities, and we choose the center of mass of this polytope as our interpolation result.

The paper explains the scheme in more detail, includes an algorithm, computational hardness results, an approximation scheme that derives from existing work, a tractable case when the DAG is a tree, and a discussion of alternate schemes.


---

