Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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$)]

share|improve this question
    
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 Dec 27 '12 at 18:43
    
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 Dec 27 '12 at 18:50
2  
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? –  JɛffE Dec 27 '12 at 19:24
1  
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ɛffE: 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? –  a3nm Dec 27 '12 at 20:01
    
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 Dec 27 '12 at 20:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.