Algorithms for Locating Facilities under Uncertainties
| dc.contributor.author | Nagarajan, Chandrashekhar | |
| dc.date.accessioned | 2008-09-17T17:49:53Z | |
| dc.date.available | 2013-09-17T06:23:09Z | |
| dc.date.issued | 2008-09-17T17:49:53Z | |
| dc.description.abstract | One of the main challenges in the area of discrete optimization is to find efficient and effective ways of solving problems that arise in day-to-day life. Traditionally, algorithms for such problems require complete knowledge of input parameters which is often undesirable and unrealistic. In this dissertation we consider some well-known hard location problems when the input parameters are not completely known in advance and design efficient algorithms for such scenarios guaranteeing quality of output solutions. In the first part of the dissertation we give a general framework and algorithmic approach for incremental approximation algorithms. Given a notion of ordering on solutions of different cardinalities, we give solutions for all cardinalities such that the solutions respect the ordering and our solution is close in value to the value of an optimal solution of cardinality k for all values of k. We apply our framework to the incremental version of the k-median problem, k-MST problem, k-vertex cover problem, k-set cover problem and the facility location problem and give new or improved incremental algorithms for these problems. We also show that our framework applies to hierarchical clustering problems. In the second part we consider the problem of leasing facilities over time where a newly arriving demand has to be either assigned to a previously leased open facility or to a newly leased facility. The serving cost of a demand can be defined as its distance from its assigned facility. The goal of the problem is to buy a set of leases at different facilities that minimizes the sum of leasing and serving costs. We give the first constant factor approximation algorithm for the offline version of the problem achieving a factor of 3. We also give the first deterministic algorithm for the online version that is O(K log n)-competitive where K is the number of available facility leases and n is the number of clients. We also compare the running times and quality of the solutions given by our incremental and hierarchical k-median algorithms with existing algorithms on different k-median datasets and verify that the quality of our solutions are better than the solutions of existing algorithms. | en_US |
| dc.identifier.other | bibid: 6563843 | |
| dc.identifier.uri | https://hdl.handle.net/1813/11387 | |
| dc.subject | Algorithms | en_US |
| dc.subject | Approximation | en_US |
| dc.subject | Optimization | en_US |
| dc.subject | Location Problems | en_US |
| dc.title | Algorithms for Locating Facilities under Uncertainties | en_US |
Files
Original bundle
1 - 1 of 1