This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is 0(log n)-competitive under these various models, where n is the total number of customers. It also shows that the algorithm is O(l)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice. © 2004 Elsevier Inc. All rights reserved.

A simple and deterministic competitive algorithm for online facility location / Anagnostopoulos, Aristidis; Russell, Bent; Eli, Upfal; P., Van Hentenryck. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 194:2 SPEC. ISS.(2004), pp. 175-202. [10.1016/j.ic.2004.06.002]

A simple and deterministic competitive algorithm for online facility location

ANAGNOSTOPOULOS, ARISTIDIS;
2004

Abstract

This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is 0(log n)-competitive under these various models, where n is the total number of customers. It also shows that the algorithm is O(l)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice. © 2004 Elsevier Inc. All rights reserved.
2004
competitive ratio; online facility location; stochastic analysis
01 Pubblicazione su rivista::01a Articolo in rivista
A simple and deterministic competitive algorithm for online facility location / Anagnostopoulos, Aristidis; Russell, Bent; Eli, Upfal; P., Van Hentenryck. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 194:2 SPEC. ISS.(2004), pp. 175-202. [10.1016/j.ic.2004.06.002]
File allegati a questo prodotto
File Dimensione Formato  
VE_2004_11573-341813.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 491.09 kB
Formato Adobe PDF
491.09 kB Adobe PDF   Contatta l'autore

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/11573/341813
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 44
  • ???jsp.display-item.citation.isi??? 29
social impact