New answers tagged approximation-algorithms
1
Your question is underspecified.
If you just want to fill the gaps, put some fixed arbitrary value there.
To make the question interesting you have to specific some condition for preferring one way of filling the gaps vs. another one.
Essentially what metric are you trying to optimize?
E.g. are you assuming that your data is a sample coming from some ...
2
In stats I think they'd say "imputation". CS theorists might model this as "matrix completion" (if you make it a matrix), "collaborative filtering" (like in the Netflix challenge). Maybe others know of more keywords.
1
This problem should be NP-hard by reducing from the maximum length of s-t paths.
The reduction simply replace every edge by, say, $k$ parallel edges. (If you are uncomfortable with a multi-graph, replace each edge by a path of length 2.) The effect of this is that the number $C_{\ell}$ of paths of length $\ell$ becomes $k^\ell C_{\ell}$. Thus, if $k$ is ...
Top 50 recent answers are included
