Return to search

Online problems in facility location

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.

Identiferoai:union.ndltd.org:MANITOBA/oai:mspace.lib.umanitoba.ca:1993/8452
Date22 August 2012
CreatorsMehrabidavoodabadi, Saeed
ContributorsDurocher, Stephane (Computer Science), Li, Ben (Computer Science) Morrison, Jason (Biosystems Engineering)
Source SetsUniversity of Manitoba Canada
Detected LanguageEnglish

Page generated in 0.0015 seconds