Large-scale Graph Analysis: System, Algorithm and Optimization by Yingxia Shao & Bin Cui & Lei Chen

Author:Yingxia Shao & Bin Cui & Lei Chen
Language: eng
Format: epub
ISBN: 9789811539282
Publisher: Springer Singapore

Proof

Let s i =min1≤j≤Kw ij which indicates the minimal cost of ith G psi processed across all the K workers and each w ij is positive integer in our problem.

Then let the lower bound of the cost for n G psi as

It is easy to infer that . Let f(n) represent the overall cost obtained by the greedy algorithm. Each time when ith G psi is distributed to worker k, the following inequations are held:

(4.5)

Algorithm 3 Distribution strategy summary

We next prove the theorem by inducing the task id. (1)i = 1, f(1) = s 1 ≤ g(1)

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.