"Fast Response" Locating a Proxy Server for the network

+1 vote
"Fast response". A series of client machines are located along a linear network. The i-th client generates amount of traffic that is given by w[i]. You want to put a server somewhere along the linear network that minimizes the total amount of traffic carried by the network. Provide an O(n) algorithm to identify the location of the server.
asked Jul 12 in Greedy Algorithms by Baijun Xie AlgoStar (400 points)

1 Answer

+1 vote
 
Best answer

Greedy algorithm works fine.

  1. Iterate the weight array from left to right and find out the TOTAL weight.  // This step takes O(n) time
  2. Iterate the weight array again from right to left and find the point at which the accumulated weight meets or exceeds half of total weight.  Put the proxy server on that location.

Examples:

Given [1, 1, 1, 1], put the proxy server on the 2nd server

Given [1,2,3,4], put the proxy server on the 3rd server.

Given [1,2,3,10], put the proxy server on the 4th server.

Given [10,1,1,1,1,1,1], put the proxy server on the 1st server.

answered Jul 12 by Amrinder Arora (206 points)
selected Jul 18 by Baijun Xie
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...