On-Line Server Algorithms Public Deposited
Downloadable ContentDownload PDF
The server problem consists of a complete graph of mobile servers, and a request sequence, which consists of vertex names. Each of the servers initially covers, i.e. is located on , one of the vertices. Servers are then moved in response to each request in f7, such that after each request the most recently requested vertex is covered. The cost to handle each request is the edge-cost of the edge along which a server moves. If a request occurs for vertex i while a server remains on i from some previous request, or i was initially covered by a server which has not moved , then the request need incur no cost. The total cost to handl e a request sequence is the sum of the costs of individual server movements. The problem, then , is to schedule the server movements in such a way that the schedule results in the minimum total cost.