Optimal Servers Placement in the Presence of Competition
Date Issued
2006
Date
2006
Author(s)
Chung, Yi-Min
DOI
en-US
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.
Subjects
競爭
動態規劃
副本
伺服器
competition
dynamic programming
replica
NP-compete
server
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93922112-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):e438e535ab51457380cfdbdb9a615181