Suppose we want to replicate a file over a collection of n servers, labeled S, S, ..., S.. To place a copy of the file at server S, results in a placement cost of Ci, for an integer ci >0. Now, if a user requests the file from server Si, and no copy of the file is present at Si, then the servers Si, Si, S. are searched in order until a copy of the file is finally found, say at server Sj where j > i. This results in an access cost ofj-i. (Note that the lower-indexed servers i-1, S-2,... are not consulted in this search.) The access cost is 0 if Si holds a copy of the file. We will require that a copy of the file be placed at server S., so that all such searches will terminate, at the latest, at S. We'd like to place copies of the files at the servers so as to minimize the sum of placement and access costs. Formally, we say that a configuration is a choice, for each server with - 1,2,..,n-1, of whether to place a copy of the file at S, or not. (Recall that a copy is always placed at S.) The total cost of a configuration is the sum of all placement costs for servers with a copy of the file, plus the sum of all access costs associated with all n servers. Give a polynomial -time algorithm to find a configuration of the minimum total cost. What is the running time of your algorithm? Suppose we want to replicate a file over a collection of n servers, labeled S, S, ..., S.. To place a copy of the file at server S, results in a placement cost of Ci, for an integer ci >0. Now, if a user requests the file from server Si, and no copy of the file is present at Si, then the servers Si, Si, S. are searched in order until a copy of the file is finally found, say at server Sj where j > i. This results in an access cost ofj-i. (Note that the lower-indexed servers i-1, S-2,... are not consulted in this search.) The access cost is 0 if Si holds a copy of the file. We will require that a copy of the file be placed at server S., so that all such searches will terminate, at the latest, at S. We'd like to place copies of the files at the servers so as to minimize the sum of placement and access costs. Formally, we say that a configuration is a choice, for each server with - 1,2,..,n-1, of whether to place a copy of the file at S, or not. (Recall that a copy is always placed at S.) The total cost of a configuration is the sum of all placement costs for servers with a copy of the file, plus the sum of all access costs associated with all n servers. Give a polynomial -time algorithm to find a configuration of the minimum total cost. What is the running time of your algorithm
