Optimal Servers Placement in the Presence of Competition

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.1 Introduction 1 2 Problem Formulation 3 3 Finding Extra Server Locations 6 3.1 k-extra-server Solution 6 3.1.1 Isolation Results 7 3.1.2 Terminal Conditions 10 3.1.3 Recursion 10 3.1.4 Time Complexity Analysis 12 3.2 Extra-server Solution 13 3.2.1 Terminal Conditions 13 3.2.2 Recursion 13 3.2.3 Time Complexity Analysis 14 4 NP-Completeness and Heuristic 15 4.1 NP-Completeness 15 4.2 A Greedy Heuristic 16 5 Experimental Results 17 5.1 Experimental Setting 18 5.2 Effect of alpha 18 5.3 Effect of Number of Original Servers 19 5.4 Effect of k 19 6 Conclusion 2