Online problems in facility location
| dc.contributor.author | Mehrabidavoodabadi, Saeed | |
| dc.contributor.examiningcommittee | Li, Ben (Computer Science) Morrison, Jason (Biosystems Engineering) | en_US |
| dc.contributor.supervisor | Durocher, Stephane (Computer Science) | en_US |
| dc.date.accessioned | 2012-08-22T20:08:35Z | |
| dc.date.available | 2012-08-22T20:08:35Z | |
| dc.date.issued | 2012-08-22 | |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| dc.description.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. | en_US |
| dc.description.note | October 2012 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/8452 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | Algorithms | en_US |
| dc.subject | Facility Location Problems | en_US |
| dc.subject | Online Algorithms | en_US |
| dc.title | Online problems in facility location | en_US |
| dc.type | master thesis | en_US |