The server allocation with boundedsimultaneous requests problem arises in isolatedinfostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterizedby a temporal interval anda category, an integer k, andan integer hc for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assignedto the same server at the same time, out of which at most hc are of category c, andthe 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 - 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, and the sum of the bandwidth rates of the simultaneous requests assigned to the same server at the same time is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain bin-packing, multiprocessor task scheduling, and interval graph coloring as special cases, and they admit on-line algorithms providing constant approximations.

Allocating servers in infostations for bounded simultaneous requests

BERTOSSI, ALAN ALBERT;
2004

Abstract

The server allocation with boundedsimultaneous requests problem arises in isolatedinfostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterizedby a temporal interval anda category, an integer k, andan integer hc for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assignedto the same server at the same time, out of which at most hc are of category c, andthe 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 - 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, and the sum of the bandwidth rates of the simultaneous requests assigned to the same server at the same time is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain bin-packing, multiprocessor task scheduling, and interval graph coloring as special cases, and they admit on-line algorithms providing constant approximations.
A.A. Bertossi; M.C. Pinotti; R. Rizzi; P. Gupta
File in questo prodotto:
Eventuali allegati, non sono esposti

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: https://hdl.handle.net/11585/10002
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact