Server Placement in the Presence of Competition.
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
4459 LNCS
Pages
124-135
Date Issued
2007
Author(s)
Abstract
This paper addresses the optimization problems of placing servers in the presence of competition. We place a set of extra servers on a graph to compete with the set of original servers. Our objective is to find the placement that maximizes the benefit, which is defined as the profits from the requests made to the extra servers despite the competition, minus the cost of constructing those 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 for finding the optimal placement of extra servers that maximizes 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 a greedy heuristic for the problems. Experiment results indicate that the greedy heuristic achieves good results, even when compared with the upper bounds found by a linear programming algorithm. The greedy heuristic yields performances within 15% of the upper bound in the worst case, and within 2% of the same theoretical upper bound on average. © Springer-Verlag Berlin Heidelberg 2007.
Other Subjects
Algorithms; Competition; Cost effectiveness; Dynamic programming; Linear programming; Optimization; Problem solving; Dynamic programming algorithm; Greedy heuristic; Optimal placement; Optimization problems; Servers
Type
conference paper