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.
| Identifer | oai:union.ndltd.org:MANITOBA/oai:mspace.lib.umanitoba.ca:1993/8452 |
| Date | 22 August 2012 |
| Creators | Mehrabidavoodabadi, Saeed |
| Contributors | Durocher, Stephane (Computer Science), Li, Ben (Computer Science) Morrison, Jason (Biosystems Engineering) |
| Source Sets | University of Manitoba Canada |
| Detected Language | English |
Page generated in 0.002 seconds