Efficient Embedding of Functions in Weighted Communication Networks.
Pooja Vyavahare, Nutan Limaye, Deepika Revankar Manjunath · arXiv (Cornell University) · 2014
Abstract—We consider the problem of efficient distributed computation of arbitrary function on arbitrary communication network. The algorithm to compute the function is given by computation graph G which is represented by weighted directed acyclic graph (DAG) and the communication network is repre-sented by a weighted graph N. We consider two variations of the problem. First we consider the problem of minimizing delay of comput-ing the function. We prove that the problem is NP-hard when computation graph is a DAG and the communication network is arbitrary. We give an algorithm which solves this problem when the computation graph is tree structured in O(pn2) time where p and n are the number of vertices in G and N, respectively. Then we looked at the problem of minimizing the cost of computing the function. We prove that this problem is also NP-hard for arbitrary computation and communication graph. There are many polynomial-time algorithms available in the literature when the computation graph is a tree. We give a polynomial-time algorithm when the computation graph is layered and takes O(rn2k) where r is the number of layers in G and k is the maximum number of vertices at any layer. I.