Name
Abstract | ||
|---|---|---|
We consider a server location problem with only one server to move. In this paper we assume that a request is given as a region and that the service can be done anywhere inside the region. Namely, for each request an online algorithm chooses an arbitrary point in the region and moves the server there. Note that if every request is a single point and the server must exactly go there in the given order as conventional server problems, there is no choice for the online player and the problem is trivial. Our main result shows that if the region is a regular n-gon, the competitive ratio of the greedy algorithm is 1/sin@p2n for odd n, and 1/sin@pn for even n. In particular for a square region, the greedy algorithm turns out to be optimal. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ipl.2008.03.025 | Inf. Process. Lett. |
Keywords | Field | DocType |
conventional server problem,. on-line algorithms,server location problem.,competitive ratio,square region,greedy algorithm,server location problem,competitive analysis,online player,regular polygon,online algorithm,arbitrary point,single point,odd n,analysis of algorithms | Discrete mathematics,Online algorithm,Combinatorics,Information processing,Analysis of algorithms,Greedy algorithm,Regular polygon,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
108 | 3 | 0020-0190 |
Citations | PageRank | References |
2 | 0.41 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. Fujiwara | 1 | 73 | 14.23 |
| Kazuo Iwama | 2 | 1400 | 153.38 |
| Kouki Yonezawa | 3 | 17 | 4.05 |