MSpace - DSpace at UofM >
Faculty of Graduate Studies (Electronic Theses and Dissertations) >
FGS - Electronic Theses & Dissertations (Public) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1993/8452

Title: Online problems in facility location
Authors: Mehrabidavoodabadi, Saeed
Supervisor: Durocher, Stephane (Computer Science)
Examining Committee: Li, Ben (Computer Science) Morrison, Jason (Biosystems Engineering)
Graduation Date: October 2012
Keywords: Algorithms
Facility Location Problems
Online Algorithms
Issue Date: 22-Aug-2012
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.
URI: http://hdl.handle.net/1993/8452
Appears in Collection(s):FGS - Electronic Theses & Dissertations (Public)

Files in This Item:

File Description SizeFormat
Mehrabidavoodabadi_Saeed.pdf532.55 kBAdobe PDFView/Open
View Statistics

Items in MSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! MSpace Software Copyright © 2002-2010  Duraspace - Feedback