在競爭環境下的最佳伺服器放置方法

Abstract

This paper proposes optimization problems for placing servers in the presence of competition. We place a set of extra servers into a graph to compete with a set of previously placed original servers. We would like to find a placement so that the benefit is maximized, which is defined as the profits from the requests coming to the extra servers despite of the competition, minus the construction cost of building extra servers. We propose an O(|V|^3k) time dynamic programming algorithm to find the optimal placement of k extra servers that maximizes the benefit in a tree with |V| nodes. We also propose an O(|V|^3) time dynamic programming algorithm that finds the optimal placement of extra servers which maximize the benefit, without any constraint on the number of extra servers. For general connected graphs, we prove that the optimization problems are NP-complete. As a result we present greedy heuristics for the problems. Experimental results indicate that the greedy heuristics achieve good results, even compared with upper bounds found by linear programming. The experimental results indicate that the greedy heuristics yields performances within 15% of the upper bound and in average within 2% of the same theoretical upper bound.