Online problems in facility location
Loading...
Date
2012-08-22
Authors
Mehrabidavoodabadi, Saeed
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We introduce two online models for the vertex k-center and the vertex k-median problems.
Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges)
are revealed sequentially, determining the topology of a graph over time. Clients are
revealed by an adversary to an online algorithm that selects existing graph vertices
on which to open facilities; once open, a facility cannot be removed or relocated. We
define two models: an online algorithm may be restricted to open a facility only at
the location of the most recent client or at the location of any existing client. We
examine these models on three classes of graphs under two types of adversaries. We
establish lower bounds on the respective competitive ratios attainable by any online
algorithm for each combination of model, adversary, and graph class. Finally, we
describe algorithms whose competitive ratios provide corresponding upper bounds on
the best competitive ratios achievable.
Description
Keywords
Algorithms, Facility Location Problems, Online Algorithms