Given a set of service requests, each characterized by a temporal interval and a category, an integer k , and an integer h_c for each category c , the Server Allocation with Bounded Simultaneous Requests problem consists in assigning a server to each request in such a way thatat most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most hc are of category c , and the minimum number of servers is used. Since this problem is computationally intractable, a 2-approximation on-line algorithm is exhibited which asymptotically gives a (2 - \frac{h}{k})-approximation, where h = \min \{ h_c \}. Generalizations of the problem are considered, where each request r is also characterized by a bandwidth rate wr, and the sum of the bandwidth rates of the simultaneous requests is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain Bin-Packing and Multiprocessor Task scheduling as special cases, and they admit on-line algorithms providing constant approximations.

Allocating Servers in Infostations for On-Demand Communications

RIZZI, ROMEO;
2003

Abstract

Given a set of service requests, each characterized by a temporal interval and a category, an integer k , and an integer h_c for each category c , the Server Allocation with Bounded Simultaneous Requests problem consists in assigning a server to each request in such a way thatat most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most hc are of category c , and the minimum number of servers is used. Since this problem is computationally intractable, a 2-approximation on-line algorithm is exhibited which asymptotically gives a (2 - \frac{h}{k})-approximation, where h = \min \{ h_c \}. Generalizations of the problem are considered, where each request r is also characterized by a bandwidth rate wr, and the sum of the bandwidth rates of the simultaneous requests is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain Bin-Packing and Multiprocessor Task scheduling as special cases, and they admit on-line algorithms providing constant approximations.
0769519261
task intervals; server allocation; scheduling; assignment; job-machine assignment; 2-approximation; online algorithm; approximation algorithm
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/436143
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact